Projekt: Strukturelle Untersuchungen dünner Mengen in NSPACE(log n)

Duration: seit 1992

Keywords: Komplexitätstheorie, nichtdeterministischer logarithmischer Platz, schreibbare Mengen <

Objectives:

Innerhalb des Projekts konnten interessante neue Charakterisierungen eines speziellen Typs dünner Mengen, der schreibbaren Mengen in NSPACE(log n), gefunden werden.Nachdem im Vorjahr von den NL-schreibbaren Mengen nachgewiesen werden konnte, daß diese Klasse genau aus den Mengen besteht, deren ranking-Funktionen innerhalb von 1NL berechnet werden könnten, ist es gelungen, weitere interessante Charakterisierungen der schreibbaren Mengen zu finden. Insbesondere ist es gelungen, Eigenschaften zu identifizieren, die für die Schreibbarkeit einer Menge verantwortlich sind. Eine entscheidende Rolle spielt dabei die Fähigkeit, eine Kopie der bisher gelesenen Eingabe wiederzuerkennen. Eine bislang offene Frage, nämlich die Frage, ob die NL-schreibbaren Mengen vollständige Sprachen besitzen, konnte positiv beantwortet werden.Weiterhin konnte nachgewiesen werden, daß die NL-schreibbaren Mengen genau die Klasse der Sprachen ist, die bezüglich einer speziellen Art von nichtdeterministisch berechenbaren Abbildungen isomorph zu den unären Mengen in NL sind. Jede NL-schreibbare Menge ist also im Prinzip nur eine unäre Menge, deren Elemente umbenannt wurden. Schließlich ist es noch gelungen, die NL-schreibbaren Mengen vermittels nicht-deterministischer Kolmogorov-Komplexität zu charakterisieren.