PSpace umfasst alle Probleme, die ein Algorithmus mit polynomiellem Arbeistspeicher lösen kann. Das sind schon eine ganze Menge: PSpace enthält alle Probleme in NP und coNP und (vermutlich) noch einiges mehr. Was SAT für NP ist, dass ist das Problem der wahren quantifizierten Booleschen Formlen (TrueQBF) für PSpace. Abgesehen davon wollen wir aber auch noch ein paar erste spielerischere Probleme dieser Klasse kennenlernen (Schach ist nicht dabei, denn das ist noch schwerer).
► Playliste für diesen Videokurs: • Theoretische Informati...
► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/Th... (11. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dresden.de/web/Th...
► Fehler gefunden? Issues melden auf github: github.com/knowsys/TheoLog
Das Beispiel des Schachproblems habe ich von Moore und Mertens: www.nature-of-computation.org/
Негізгі бет PSpace: Schwerer als NP (aber leichter als Schach)
Пікірлер