PRZESTRZEŃ - PSPACE
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 wielomianu ilość miejsca .
Formalna definicja
Jeśli oznaczymy SPACE( t ( n ) ), zbiór wszystkich problemów, które mogą być rozwiązane przez maszyny Turinga przy użyciu przestrzeni O ( t ( n )) dla jakiejś funkcji t o wielkości wejściowej n , to możemy zdefiniować PSPACE formalnie jako
PSPACE jest ścisłym nadzbiorem zestawu języków kontekstowych .
Okazuje się, że umożliwienie maszynie Turinga bycia niedeterministycznym nie dodaje żadnej dodatkowej mocy. Ze względu na twierdzenie Savitcha, NPSPACE jest równoważne PSPACE, zasadniczo dlatego, że deterministyczna maszyna Turinga może symulować niedeterministyczną maszynę Turinga bez potrzeby dużo więcej miejsca (nawet jeśli może zużywać znacznie więcej czasu). Ponadto dopełnienia wszystkich problemów w PSPACE są również w PSPACE, co oznacza, że co-PSPACE = PSPACE.
Relacja między innymi klasami
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 ograniczanie, nie jest tym samym co ⊈):
Z trzeciego wiersza wynika, że zarówno w pierwszym, jak i drugim wierszu przynajmniej jeden z zestawów musi być ścisły, ale nie wiadomo który. Powszechnie podejrzewa się, że wszyscy są surowi.
Wiadomo, że ograniczenia w trzeciej linii są surowe. Pierwszy wynika z bezpośredniej diagonalizacji ( twierdzenie o hierarchii przestrzeni , NL ⊊ NPSPACE) oraz faktu, że PSPACE = NPSPACE poprzez twierdzenie Savitcha . Drugie wynika po prostu z twierdzenia o hierarchii przestrzeni.
Najtrudniejszymi problemami w PSPACE są problemy PSPACE-zupełne. Zobacz PSPACE-complete dla przykładów problemów, które są podejrzewane o PSPACE, ale nie w NP.
Właściwości zamknięcia
Klasa PSPACE jest zamknięta w ramach unii operacyjnej , komplementarności i gwiazdy Kleene .
Inne charakterystyki
Alternatywną charakterystyką PSPACE jest zestaw problemów rozstrzyganych przez przemienną maszynę Turinga w czasie wielomianowym, czasami nazywany APTIME lub po prostu AP.
Logiczna charakterystyka PSPACE na podstawie opisowej teorii złożoności polega na tym, że jest to zestaw problemów wyrażalnych w logice drugiego rzędu z dodatkiem przechodniego operatora domknięcia . Pełne zamknięcie przechodnie nie jest potrzebne; wystarczą przemienne domknięcie przechodnie i jeszcze słabsze formy. To właśnie dodanie tego operatora (ewentualnie) odróżnia PSPACE od PH .
Głównym wynikiem teorii złożoności jest to, że PSPACE można scharakteryzować jako wszystkie języki rozpoznawalne przez określony interaktywny system dowodowy , ten definiujący klasę IP . W tym systemie istnieje wszechmocny dowód, który próbuje przekonać losowy weryfikator w czasie wielomianowym, że łańcuch jest w języku. Powinien być w stanie przekonać weryfikator 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 to także P CTC , problemy rozwiązywane przez klasyczne komputery przy użyciu zamkniętych krzywych czasopodobnych , a także BQP CTC , problemy rozwiązywane przez komputery kwantowe przy użyciu zamkniętych krzywych czasopodobnych.
PSPACE-kompletność
Język B jest PSPACE-kompletny, jeśli znajduje się w PSPACE i jest PSPACE-twardy, co oznacza dla wszystkich A ∈ PSPACE, , gdzie oznacza, że istnieje wielomianowa redukcja z A do B . Problemy PSPACE-zupełne mają ogromne znaczenie w badaniu problemów PSPACE, ponieważ stanowią one najtrudniejsze problemy w PSPACE. Znalezienie prostego rozwiązania problemu z PSPACE-zupełnym oznaczałoby, że mamy proste rozwiązanie wszystkich innych problemów w PSPACE, ponieważ wszystkie problemy z PSPACE można by zredukować do problemu z PSPACE-zupełnym.
Przykładem problemu PSPACE-zupełny jest problem ilościowego wzoru logicznego (zwykle skracany do QBF lub TQBF ; T oznacza „prawda”).
Bibliografia
- Arora, Sanjeev ; Barak, Boaz (2009). Złożoność obliczeniowa. Nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Sipser, Michael (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. Numer ISBN 0-534-94728-X. Sekcja 8.2–8.3 (Klasa PSPACE, PSPACE-kompletność), s. 281–294.
- Papadimitriou, Christos (1993). Złożoność obliczeniowa (wyd. 1). Addisona Wesleya. Numer ISBN 0-201-53082-1. Rozdział 19: Przestrzeń wielomianowa, s. 455–490.
- Sipser, Michael (2006). Wprowadzenie do teorii obliczeń (wyd. 2). Technologia kursu Thomsona. Numer ISBN 0-534-95097-3. Rozdział 8: Złożoność przestrzeni
- Złożoność Zoo : PSPACE