03.10.2024 –, B002 - Trockendock
Language: Deutsch
Wie kann man in einem Falltürenlabyrinth mit sehr viel Rechenzeit, aber enorm wenig Speicherplatz, herausfinden, ob darin ein Schatz versteckt ist? (Satz von Immerman und Szelepcsenyi)
Vorgestellt wird folgende Frage: in einem Irrgarten, den man beliebig oft durchlaufen kann und bei dem jeder Raum mit zwei weiteren Räumen verbunden ist, man aber nach dieser Entscheidung nicht wieder zurückgehen kann (Falltürenlabyrinth), wird nach einem Schatz gesucht. Dabei steht beliebig viel Zeit, aber fast gar kein Speicherplatz zur Verfügung. Insbesondere ist es nicht möglich, eine vollständige Karte vom Labyrinth zu zeichnen. Wie kann man trotzdem herausfinden, ob es tatsächlich einen Schatz im Labyrinth gibt?
Die Frage veranschaulicht den Beweis von Immerman und Szelepcsenyi, der zeigt, dass nichtdeterministische Raumkomplexitätsklassen (NSPACE-Klassen) unter Komplement abgeschlossen sind.
Begeistert für Fahrkarten und Theoretische Informatik.