Twierdzenie o hierarchii przestrzennej

W teorii złożoności obliczeniowej twierdzenia o hierarchii przestrzennej są wynikami separacji, które pokazują, że zarówno deterministyczne, jak i niedeterministyczne maszyny mogą rozwiązywać więcej problemów w (asymptotycznie) większej przestrzeni, z zastrzeżeniem pewnych warunków. Na przykład deterministyczna maszyna Turinga może rozwiązać więcej problemów decyzyjnych w przestrzeni n log n niż w przestrzeni n . Nieco słabszymi analogicznymi twierdzeniami dotyczącymi czasu są twierdzenia o hierarchii czasu .

Podstawą twierdzeń o hierarchii jest intuicja, że ​​im więcej czasu, albo więcej miejsca, to możliwość obliczania większej liczby funkcji (lub decydowania o większej liczbie języków). Twierdzenia o hierarchii służą do wykazania, że ​​klasy złożoności czasu i przestrzeni tworzą hierarchię, w której klasy o węższych granicach zawierają mniej języków niż te o luźniejszych granicach. Tutaj zdefiniujemy i udowodnimy twierdzenie o hierarchii przestrzeni.

Twierdzenia o hierarchii przestrzennej opierają się na koncepcji funkcji konstruowalnych w przestrzeni . Twierdzenia o deterministycznej i niedeterministycznej hierarchii przestrzeni stwierdzają, że dla wszystkich konstruowalnych w przestrzeni funkcji f ( n ),

$\ Displaystyle {\ mathsf {PRZESTRZEŃ}} \ lewo (o (f (n)) \ prawo) \ podzbiór {\mathsf {SPACJA}}(f(n))}$ ,

gdzie SPACE oznacza DSPACE lub NSPACE , a o odnosi się do małej notacji o .

Oświadczenie

$geq$ funkcja konstruowalna w przestrzeni, jeśli $fa$ i istnieje maszyna Turinga, która oblicza funkcję w przestrzeni ${\ Displaystyle f (n)}$${\ Displaystyle O (f (n)}}$ zaczynając $reprezentuje$$.$ gdzie ciąg kolejnych jedynek Większość typowych funkcji, z którymi pracujemy, jest konstruowalna w przestrzeni, w tym wielomiany, wykładniki i logarytmy.

$O (f (n))}$ każdej funkcji konstruowalnej w przestrzeni $n$ L, który jest rozstrzygalny przestrzeni ${$ , ale nie w przestrzeni ${\ Displaystyle o (f (n))}$ .

Dowód

Celem jest zdefiniowanie języka, który można rozstrzygnąć w przestrzeni, $)) )}$ przestrzeni $Displaystyle$ . Język jest zdefiniowany jako L :

${\ Displaystyle L = \ {~ (\ langle M \ rangle, 10 ^ {k}): M {\ mbox {używa spacji}} \ równoważnik f (| \ langle M \ rangle, 10 ^ {k} | ){\mbox{ i czas }}\leq 2^{f(|\langle M\rangle ,10^{k}|)}{\mbox{ i }}M{\mbox{ nie akceptuje }}(\ kąt M\rangle ,10^{k})~\}}$

Dla dowolnej maszyny M , która decyduje o języku w przestrzeni , L będzie się różnić przynajmniej w jednym miejscu od języka M. o $}$ ) Mianowicie, dla niektórych wystarczająco dużych k , M użyje spacji ${\ Displaystyle \ równoważnik f (| \ langle M \ rangle, 10 ^ {k} |)}$ na ${\ Displaystyle (\ langle M \ rangle, 10 ^ {k})}$ i dlatego będzie się różnić swoją wartością.

Z drugiej strony L jest w $\ Displaystyle {\ mathsf {PRZESTRZEŃ}} (f (n))$ } Algorytm decydowania o języku L jest następujący:

1. $_$ wejściu x oblicz $używając$ constructibility _ $podejmowana$ próba użycia więcej ,
2. Jeśli x nie ma $_$ dla TM _ _
3. Symuluj M na wejściu x przez co najwyżej ${\ Displaystyle 2 ^ {f (| x |)}}$ kroków (używając spacji ${\ Displaystyle f (| x |) }$ . Jeśli symulacja próbuje użyć więcej niż ${f (| x |)$ niż $Displaystyle 2$ operacji, a następnie odrzucić .
4. Jeśli M zaakceptował x podczas tej symulacji, to odrzuć ; w przeciwnym razie zaakceptuj .

$jest$ ograniczone do uniknąć sytuacji, w której się na wejściu x $zużywa$ przypadek, w którym przestrzeń zgodnie wymaganiami, ale działa przez

Powyższy dowód dotyczy przypadku PSPACE, ale w przypadku NPSPACE należy wprowadzić pewne zmiany. Kluczową kwestią jest to, że podczas gdy w deterministycznej TM akceptację i odrzucenie można odwrócić (kluczowe dla kroku 4), nie jest to możliwe na maszynie niedeterministycznej.

W przypadku NPSPACE L należy najpierw przedefiniować:

${\ Displaystyle L = \ {~ (\ langle M\rangle ,10^{k}):M{\mbox{ używa spacji }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ i }}M{\mbox{ akceptuje }}(\langle M\rangle ,10^{k})~\}}$

Teraz algorytm musi zostać zmieniony, aby akceptował L , modyfikując krok 4 na:

• Jeśli M zaakceptował x podczas tej symulacji, to zaakceptuj ; w przeciwnym razie odrzucić .

L nie $użyciu$ TM Zakładając , że L może być określone przez jakąś TM M $komórek$ użyciu i zgodnie z Immermana – Szelepcsényi $}}$$Displaystyle {\ overline {$ można również określić za pomocą TM (nazywanej ${\ Displaystyle {\ overline {M}}}$ ) przy użyciu komórek ${\ Displaystyle o (f (n))} .$ Tu leży sprzeczność, więc założenie musi być fałszywe:

1. w ${\ Displaystyle w = (\ langle {\ overline {M}} \ rangle, 10 ^ {k})}$ dla niektórych wystarczająco dużych k ) nie jest w $displaystyle {\ overline {L}}}$${$ \ wtedy M zaakceptuje to, dlatego $odrzuca$ w , dlatego w jest w $}}$ (sprzeczność).
2. w ${\ Displaystyle w = (\ langle {\ overline {M}} \ rangle, 10 ^ {k})}$ dla niektórych wystarczająco dużych k ) jest w ${\ displaystyle {\ overline {L}}}$ wtedy M odrzuci go, dlatego $akceptuje$ w , dlatego w nie jest w $}}$ { \ displaystyle {\ overline (sprzeczność).

Porównanie i ulepszenia

Twierdzenie o hierarchii przestrzeni jest silniejsze niż analogiczne twierdzenia o hierarchii czasu na kilka sposobów:

• Wymaga tylko, aby s(n) było co najmniej log n zamiast co najmniej n .
• Może rozdzielać klasy z dowolną różnicą asymptotyczną, podczas gdy twierdzenie o hierarchii czasu wymaga, aby były one rozdzielone czynnikiem logarytmicznym.
• Wymaga jedynie, aby funkcja była konstrukcyjna w przestrzeni, a nie w czasie.

Wydaje się, że łatwiej jest rozdzielić klasy w przestrzeni niż w czasie. Rzeczywiście, podczas gdy twierdzenie o hierarchii czasu nie odnotowało znaczącej poprawy od czasu jego powstania, twierdzenie o niedeterministycznej hierarchii przestrzeni odnotowało co najmniej jedno ważne ulepszenie Viliama Gefferta w jego artykule z 2003 r. „Zrewidowane twierdzenie o hierarchii przestrzeni”. W tym artykule dokonano kilku uogólnień twierdzenia:

• Rozluźnia wymóg konstruowalności przestrzeni. Zamiast po prostu oddzielić klasy unii i ${\ Displaystyle {\ mathsf {DSPACE}} (o (s (n))}$$}} (O (s (n)$ ) , oddziela ${\ Displaystyle {\ mathsf {DSPACE}} (f (n))}$${\ mathsf {DSPACE}} (g$ do $($ gdzie jest dowolną funkcją $)$ { \ ${\ Displaystyle o (s (n))}$ funkcja. Funkcje te nie muszą być konstruowalne w przestrzeni ani nawet rosnące monotonicznie.
• Identyfikuje język jednoargumentowy lub język rejestracyjny, który należy do jednej klasy, ale nie do drugiej. W pierwotnym twierdzeniu język rozdzielający był dowolny.
• Nie wymaga, aby ${\ Displaystyle s (n)}$ był przynajmniej log n ; może to być dowolna niedeterministycznie w pełni konstruowalna w przestrzeni funkcja.

Uściślenie hierarchii przestrzeni

Jeśli przestrzeń jest mierzona jako liczba komórek użytych niezależnie od rozmiaru alfabetu, to ${\ Displaystyle {\ mathsf {PRZESTRZEŃ }}(f(n))={\mathsf {SPACJA}}(O(f(n)))}$ ponieważ można uzyskać dowolną kompresję liniową, przechodząc na większy alfabet. Jednak mierząc przestrzeń w bitach, można osiągnąć znacznie ostrzejszą separację dla przestrzeni deterministycznej. Zamiast być definiowana do stałej multiplikatywnej, przestrzeń jest teraz definiowana do stałej addytywnej. wewnętrznym, nadal mamy ${\ Displaystyle {\ mathsf {PRZESTRZEŃ}} (f (n)) = {\ mathsf {PRZESTRZEŃ}} (f (n) + O (1))}$ .

Załóżmy, że f jest konstruowalny przestrzennie. PRZESTRZEŃ jest deterministyczna.

• Dla szerokiej gamy sekwencyjnych modeli obliczeniowych, w tym dla maszyn Turinga, PRZESTRZEŃ ( f ( n ) - ω (log ( f ( n ) + n ))) ⊊ PRZESTRZEŃ ( f ( n )). Dzieje się tak nawet wtedy, gdy PRZESTRZEŃ( f ( n )- ω (log( f ( n )+ n ))) jest zdefiniowana przy użyciu innego ${\ Displaystyle {\ mathsf {PRZESTRZEŃ}} (f (n))},$ ponieważ różne modele mogą symulować się nawzajem za pomocą ${\ Displaystyle O (\ log (f) (n)+n))}$ miejsce na wierzchu.
• W przypadku niektórych modeli obliczeniowych mamy nawet PRZESTRZEŃ( f ( n )- ω (1)) ⊊ PRZESTRZEŃ ( f ( n )). W szczególności dotyczy to maszyn Turinga, jeśli ustalimy alfabet, liczbę głowic na taśmie wejściowej, liczbę głowic na taśmie roboczej (przy użyciu pojedynczej taśmy roboczej) i dodamy ograniczniki dla odwiedzanej części taśmy roboczej (która może sprawdzić bez zwiększania wykorzystania miejsca). SPACE( f ( n )) nie zależy od tego, czy taśma robocza jest nieskończona czy półnieskończona. Możemy również mieć stałą liczbę taśm roboczych, jeśli f ( n ) jest albo konstrukcyjną krotką SPACE podającą wykorzystanie przestrzeni na taśmę, albo konstrukcyjną liczbą SPACE( f ( n )- ω (log( f ( n ))) podającą całkowite wykorzystanie przestrzeni (nie licząc narzutu dla zapamiętywanie długości każdej taśmy).

Dowód jest podobny do dowodu twierdzenia o hierarchii przestrzeni, ale z dwoma komplikacjami: uniwersalna maszyna Turinga musi być wydajna przestrzennie, a odwrócenie musi być efektywne przestrzennie. Ogólnie można skonstruować uniwersalne maszyny Turinga z przestrzenią napowietrzną i przy odpowiednich założeniach, po prostu $($$\ Displaystyle O (\ log$$1)}$ przestrzeń napowietrzna (co może zależeć od symulowanej maszyny). W przypadku odwrócenia kluczową kwestią jest to, jak wykryć, czy symulowana maszyna odrzuca, wprowadzając nieskończoną (ograniczoną przestrzenią) pętlę. Samo zliczenie liczby wykonanych kroków zwiększyłoby zużycie miejsca o około ${\ displaystyle f (n)}$ . Kosztem potencjalnie wykładniczego wzrostu czasu, pętle można wykrywać efektywnie przestrzennie w następujący sposób:

Zmodyfikuj maszynę, aby wymazać wszystko i przejść do określonej konfiguracji A, jeśli się powiedzie. Użyj przeszukiwania w głąb, aby określić, czy A jest osiągalne w przestrzeni ograniczonej od konfiguracji początkowej. Wyszukiwanie zaczyna się od A i przechodzi przez konfiguracje, które prowadzą do A. Ze względu na determinizm można to zrobić w miejscu i bez wchodzenia w pętlę.

Można również określić, czy maszyna przekracza granicę przestrzeni (w przeciwieństwie do zapętlenia w obrębie przestrzeni ograniczonej), iterując po wszystkich konfiguracjach, które mają przekroczyć granicę przestrzeni i sprawdzając (ponownie przy użyciu wyszukiwania w głąb), czy początkowa konfiguracja prowadzi do jakiegokolwiek z nich.

Wnioski

Wniosek 1

Dla dowolnych dwóch funkcji ${\ Displaystyle f_ {1}}$ , ${\ Displaystyle f_ {2}: \ mathbb {N} \ longrightarrow \ mathbb {N}}$ , gdzie ${ \ Displaystyle f_ {1} (n)}$ jest ${\ Displaystyle o (f_ {2} (n))}$ i ${\ Displaystyle f_ {2}}$ jest konstruowalny w przestrzeni, $\ Displaystyle {\ mathsf {PRZESTRZEŃ}} (f_ {1} (n)} \ subsetneq {\ mathsf {PRZESTRZEŃ}} (f_{2}(n))}$ .

Ten wniosek pozwala nam rozdzielić różne klasy złożoności przestrzeni. Dowolna funkcja $konstruowalna$ w przestrzeni dla dowolnej liczby naturalnej k Dlatego dla dowolnych dwóch liczb naturalnych udowodnić $< k 2 {\ Displaystyle$${\ Displaystyle {\ mathsf PRZESTRZEŃ}} (n ^ {k_ {1}}) \ subsetneq {\ mathsf PRZESTRZEŃ}} (n ^ {k_ {2}})}$ . Pomysł ten można rozszerzyć na liczby rzeczywiste w następującym wniosku. Pokazuje to szczegółową hierarchię w klasie PSPACE.

Wniosek 2

Dla dowolnych dwóch nieujemnych liczb rzeczywistych ${\ Displaystyle a_ {1}<a_ {2}, {\ mathsf { SPACJA}}(n^{a_{1}})\subsetneq {\mathsf {SPACJA}}(n^{a_{2}})}$ .

Wniosek 3

NL ⊊ P PRZESTRZEŃ .

Dowód

Twierdzenie Savitcha pokazuje, że $\ Displaystyle {\ mathsf {NL}} \ subseteq {\ mathsf {PRZESTRZEŃ}} (\ log ^ {2} n)}$ że ${\ Displaystyle {\ mathsf {PRZESTRZEŃ}} (\ log ^ {2} n) \ subsetneq {\ mathsf {PRZESTRZEŃ}} (n)}$ . Rezultatem jest ten wniosek wraz z faktem, że TQBF ∉ NL, ponieważ TQBF jest PSPACE-zupełny.

Można to również udowodnić za pomocą niedeterministycznego twierdzenia o hierarchii przestrzeni, aby pokazać, że NL ⊊ NPSPACE, oraz za pomocą twierdzenia Savitcha, aby pokazać, że PSPACE = NPSPACE.

Wniosek 4

PRZESTRZEŃ ⊊ PRZESTRZEŃ .

Ten ostatni wniosek pokazuje istnienie rozstrzygalnych problemów, które są trudne do rozwiązania. Innymi słowy, ich procedury decyzyjne muszą wykorzystywać więcej niż przestrzeń wielomianową.

Wniosek 5

Istnieją problemy w PSPACE wymagające do rozwiązania dowolnie dużego wykładnika; dlatego PSPACE nie zwija się do DSPACE ( n ^k ) dla pewnej stałej k .

Zobacz też

• Twierdzenie o hierarchii czasu

•    Arora, Sanjeev ; Barak, Boaz (2009). Złożoność obliczeniowa. Nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge . ISBN 978-0-521-42426-4 . Zbl 1193.68112 .
• Luca Trevisan . Uwagi na temat twierdzeń o hierarchii . Handout 7. CS172: Automaty, obliczalność i złożoność. UC Berkeley. 26 kwietnia 2004.
• Viliama Gefferta . Twierdzenie o hierarchii przestrzeni poprawione . Informatyka teoretyczna , tom 295, nr 1–3, s. 171-187. 24 lutego 2003 r.
•   Sipser, Michael (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. ISBN 0-534-94728-X . Strony 306–310 sekcji 9.1: Twierdzenia o hierarchii.
•   Papadimitriou, Christos (1993). Złożoność obliczeniowa (wyd. 1). Addisona Wesleya. ISBN 0-201-53082-1 ​​. Sekcja 7.2: Twierdzenie o hierarchii, s. 143–146.