MRMCD 2024

Schatzsuche mit minimalem Speicherplatz
10-03, 14:00–15:30 (Europe/Berlin), B002 - dry dock
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.

See also: Präsentationsfolien (finaler Stand) (3.2 MB)

Begeistert für Fahrkarten und Theoretische Informatik.