PSpace-Vollständigkeit 1: TrueQBF und Savitchs Middle-First Suche

Ein paar typische Probleme für PSpace hatten wir schon kennengelernt (TrueQBF, Geography). Jetzt wollen wir noch etwas besser verstehen, wieso diese Probleme PSpace-vollständig sind. In diesem Video beginne ich dazu mit der PSpace-Schwere von TrueQBF (die Inklusion in PSpace hatten wir schon). Die Beweisskizze beinhaltet im Prinzip auch schon die wichtigsten Ideen, die man für den Beweis von Savitchs berühmten Satz (Eliminierung von Nichtdeterminismus in speicherbeschränkten Algorithmen) benötigt.
► Playliste für diesen Videokurs: • Theoretische Informati...
► Vorlesungsfolien zum Download: iccl.inf.tu-dr... (12. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dr...
► Fehler gefunden? Issues melden auf github: github.com/kno...