PRZESTRZEŃ

Uwzględnienie klas złożoności, w tym P , NP , co-NP , BPP , P/poly , PH i PSPACE

Nierozwiązany problem w informatyce :

${\ Displaystyle {\ mathsf {P {\ overset {?}} {=}} PSPACE}}}$

(więcej nierozwiązanych problemów w informatyce)

W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych , które mogą być rozwiązane przez maszynę Turinga przy użyciu wielomianowej ilości przestrzeni .

Definicja formalna

Jeśli oznaczymy przez PRZESTRZEŃ ( f ( n )), zbiór wszystkich problemów, które mogą być rozwiązane przez maszyny Turinga przy użyciu przestrzeni O ( f ( n )) dla jakiejś funkcji f o rozmiarze wejściowym n , to formalnie możemy zdefiniować PSPACE jako

${\ Displaystyle {\ mathsf {PRZESTRZEŃ}} = \ bigcup _ {k \ w \ mathbb {N}} {\ mathsf {PRZESTRZEŃ}} (n ^ {k}).}$

PSPACE jest ścisłym nadzbiorem zestawu języków kontekstowych .

Okazuje się, że pozwolenie, by maszyna Turinga była niedeterministyczna , nie dodaje żadnej dodatkowej mocy. Z powodu twierdzenia Savitcha , NPSPACE jest równoważne PSPACE, głównie dlatego, że deterministyczna maszyna Turinga może symulować niedeterministyczną maszynę Turinga bez potrzeby zajmowania dużo więcej miejsca (nawet jeśli może to zająć znacznie więcej czasu ). Również dopełnienia wszystkich problemów w PSPACE są również w PSPACE, co oznacza, że ​​co-PSPACE = PSPACE.

Relacja między innymi klasami

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 (zauważ, że ⊊, oznaczające ścisłe zawieranie, nie jest tym samym co ⊈):

${\ Displaystyle {\ rozpocząć {tablica} {l} {\ mathsf {NL \ subseteq P \ subseteq NP \ subseteq PH \ subseteq PSPACE}} \\ {\ mathsf {PSPACE\subseteq EXPACE\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPSPACE}}\end{array}}}$

Z trzeciego wiersza wynika, że ​​zarówno w pierwszym, jak iw drugim wierszu, co najmniej jedno z ustawionych zabezpieczeń musi być ścisłe, ale nie wiadomo, które. Powszechnie podejrzewa się, że wszyscy są surowi.

Restrykcje na trzeciej linii są znane jako surowe. Pierwsza wynika z bezpośredniej diagonalizacji ( twierdzenie o hierarchii przestrzeni , NL ⊊ NPSPACE) oraz faktu, że PSPACE = NPSPACE poprzez twierdzenie Savitcha . Drugi wynika po prostu z twierdzenia o hierarchii przestrzeni.

Najtrudniejsze problemy w PSPACE to problemy zupełne w PSPACE. Zobacz PSPACE-complete , aby zapoznać się z przykładami problemów, które prawdopodobnie występują w PSPACE, ale nie w NP.

Właściwości zamknięcia

Klasa PSPACE jest zamknięta pod operacjami suma , dopełnienie i gwiazda Kleene .

Inne charakteryzacje

Alternatywną charakterystyką PSPACE jest zbiór problemów rozstrzygalnych przez naprzemienną maszynę Turinga w czasie wielomianowym, czasami nazywaną APTIME lub po prostu AP.

Logiczna charakterystyka PSPACE z opisowej teorii złożoności polega na tym, że jest to zbiór problemów, które można wyrazić w logice drugiego rzędu z dodatkiem przechodniego operatora domknięcia . Pełne domknięcie przechodnie nie jest potrzebne; wystarczy przemienne domknięcie przechodnie i nawet słabsze formy. To dodanie tego operatora (prawdopodobnie) odróżnia PSPACE od PH .

Głównym rezultatem teorii złożoności jest to, że PSPACE można scharakteryzować jako wszystkie języki rozpoznawane przez konkretny interaktywny system dowodowy , ten definiujący klasę IP . W tym systemie istnieje wszechpotężny dowodzący, który próbuje przekonać losowy weryfikator czasu wielomianowego, że ciąg znaków jest w języku. Powinien być w stanie przekonać weryfikatora z dużym prawdopodobieństwem, jeśli ciąg jest w języku, ale nie powinien być w stanie go przekonać, chyba że z małym prawdopodobieństwem, jeśli ciąg nie jest w języku.

PSPACE można scharakteryzować jako klasę złożoności kwantowej QIP .

PSPACE jest również równe PC _CTC , problemom rozwiązywanym przez klasyczne komputery przy użyciu zamkniętych krzywych czasopodobnych , jak również BQP _CTC , problemom rozwiązywanym przez komputery kwantowe przy użyciu zamkniętych krzywych czasoprzestrzennych.

PSPACE-zupełność

Główny artykuł: PSPACE-kompletny

Język B jest PSPACE-kompletny , jeśli jest w PSPACE i jest PSPACE-twardy, co oznacza dla wszystkich, gdzie ${\ Displaystyle A \ równoważnik _ {\ tekst {P}} B}$ ∈ PSPACE , ${\ Displaystyle A \ leq _ {\ tekst {P}} B}$ oznacza, że ​​istnieje wielomianowa redukcja wielu jeden z A do B . Problemy zupełne PSPACE mają ogromne znaczenie w badaniu problemów PSPACE, ponieważ reprezentują najtrudniejsze problemy w 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 sprowadzić do problemu PSPACE-zupełnego.

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

Notatki

•    Arora, Sanjeev ; Barak, Boaz (2009). Złożoność obliczeniowa. Nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge . ISBN 978-0-521-42426-4 . Zbl 1193.68112 .
•   Sipser, Michael (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. ISBN 0-534-94728-X . Sekcja 8.2–8.3 (Klasa PSPACE, kompletność PSPACE), s. 281–294.
•   Papadimitriou, Christos (1993). Złożoność obliczeniowa (wyd. 1). Addisona Wesleya. ISBN 0-201-53082-1 ​​. Rozdział 19: Przestrzeń wielomianowa, s. 455–490.
•   Sipser, Michael (2006). Wprowadzenie do teorii obliczeń (wyd. 2). Technologia kursu Thomsona. ISBN 0-534-95097-3 . Rozdział 8: Złożoność przestrzeni
• Zoo złożoności : PSPACE