Uzupełnieniem wszystkich problemów w PSPACE jest także PSPACE, co oznacza, że co-PSPACE PSPACE.

Relacja między innymi klasami mały|prawo|300x300px|Reprezentacja relacji między klasami złożoności Znane są następujące relacje między PSPACE a klasami złożoności NL, P, NP, PH, EXPTIME i EXPSPACE (należy zwrócić uwagę, że co oznacza ścisłe zawieranie, to nie to samo co ):

Wiadomo, że w pierwszym i drugim wierszu co najmniej jedno z zawierań musi być ścisłe, ale nie wiadomo, które. Powszechnie podejrzewa się, że wszystkie są ścisłe.

PSPACE-zupełność Język jest PSPACE-zupełny, jeśli jest w PSPACE i jest trudny dla PSPACE, co oznacza dla wszystkich gdzie oznacza, że istnieje redukcja z do w czasie wielomianowym. Problemy PSPACE-zupełne mają ogromne znaczenie przy badaniu problemów z PSPACE, ponieważ stanowią najtrudniejsze problemy z PSPACE. Znalezienie prostego rozwiązania problemu PSPACE-zupełnego oznaczałoby, że mamy proste rozwiązanie wszystkich innych problemów w PSPACE, ponieważ wszystkie problemy PSPACE można zredukować do problemu PSPACE-zupełnegoArora & Barak (2009) p. 83..

Przykładem problemu pełnego PSPACE-zupełnego jest problem skwantyfikowanej boolowskiej formuły (zwykle w skrócie QBF lub TQBF ; T oznacza „prawda”).

Przypisy

Kategoria:Klasy złożoności