Dlaczego uważamy, że PSPACE ≠ EXPTIME?

Mam problem z intuicyjnym zrozumieniem, dlaczego ogólnie uważa się, że PSPACE różni się od EXPTIME. Jeśli PSPACE jest zbiorem problemów możliwych do rozwiązania w wielomianu kosmicznym w wielkości wejściowej $f(n)$ , to w jaki sposób może istnieć klasa problemów, które doświadczają większego wybuchu czasu wykładniczego i nie wykorzystują przestrzeni wykładniczej?

Odpowiedź Yuvala Filmusa jest już niezwykle pomocna. Czy jednak ktoś mógłby naszkicować mój luźny argument, dlaczego może tak być, że PSPACE ≠ EXPTIME (tj. Że PSPACE nie jest właściwym podzbiorem EXPTIME)? Czy nie potrzebujemy przestrzeni wykładniczej, aby pokonać górną granicę całkowitej liczby konfiguracji systemu możliwych do uzyskania z przestrzenią, która skaluje się wielomianowo z rozmiarem wejściowym? Wystarczy powiedzieć, że rozumiem, dlaczego EXPTIME ≠ EXPSPACE jest sprawą otwartą, ale brakuje mi zrozumienia co do związku między PSPACE a EXPTIME.

complexity-theory complexity-classes intuition

— użytkownik25876
źródło

Odświeżmy definicje.

PSPACE to klasa problemów, które można rozwiązać na deterministycznej maszynie Turinga z wielomianowymi granicami przestrzeni: to znaczy, dla każdego takiego problemu istnieje maszyna, która decyduje o problemie przy użyciu co najwyżej $p(n)$ komórek taśmowych, gdy jej wejście ma długość $n$ , dla niektórych wielomianów $p$ .
EXP to klasa problemów, które można rozwiązać na deterministycznej maszynie Turinga z wykładniczymi granicami czasowymi: dla każdego takiego problemu istnieje maszyna, która decyduje o problemie, używając co najwyżej $2^{p(n)}$ kroków, gdy jego wejście ma długość $n$ , dla jakiś wielomian $p$ .

Po pierwsze, powinniśmy powiedzieć, że te dwie klasy mogą być równe. Wydają się bardziej prawdopodobne, że będą się różnić, ale klasy czasami okazują się takie same: na przykład w 2004 r. Reingold udowodnił, że symetryczny obszar logów jest taki sam jak zwykły obszar logów; w 1987 r. Immerman i Szelepcsényi niezależnie udowodnili, że NL $\;=\;$ co-NL (i faktycznie, że NSPACE [ $f(n)$ ] $\;=\;$ co-NSPACE [ ] $f(n)$ dla dowolnego ). $f(n)\geq \log n$

Ale w tej chwili większość ludzi uważa, że PSPACE i EXP są różne. Czemu? Zobaczmy, co możemy zrobić w dwóch klasach złożoności. Rozważ problem w PSPACE . Możemy użyć komórek taśmy do rozwiązania danych wejściowych o długości ale trudno jest porównać to z EXP , który jest określony przez ograniczenie czasowe. $p(n)$ $n$

Ile czasu możemy wykorzystać na problem z PSPACE ? Gdybyśmy tylko napisać do komórek taśmowych, istnieją różne ciągi znaków, które mogą pojawić się na taśmie, przy założeniu alfabetu binarnego. Głowica taśmy może znajdować się w dowolnym z różnych miejsc, a maszyna Turinga może znajdować się w jednym z różnych stanów. Zatem łączna liczba konfiguracji wynosi $p(n)$ $2^{p(n)}$ $p(n)$ $k$ $T(n) = k\,p(n)\,2^{p(n)}\!$ . Zgodnie z zasadą szufladki, jeśli bierzemy kroki , musimy odwiedzić konfigurację dwa razy, ale ponieważ maszyna jest deterministyczna, oznacza to, że będzie się zapętlać i odwiedzać tę samą konfigurację nieskończenie często, tj. Wygrała zatrzymać. Ponieważ część definicji bycia w PSPACE polega na tym, że musisz zdecydować o problemie, każda maszyna, która się nie kończy, nie rozwiązuje problemu PSPACE . Innymi słowy, PSPACE to klasa problemów, które można rozstrzygać przy użyciu co najwyżej przestrzeni i co najwyżej $T(n)+1$ $p(n)$ , co najwyżej dla pewnego wielomianu . Więc pokazaliśmy tęPSPACE $k\,p(n)\,2^{p(n)}$ $2^{q(n)}$ $q$ $\;\subseteq\;$ EXP .

A ile miejsca możemy wykorzystać na problem z EXP ? Cóż, wolno nam kroków, a głowa maszyny Turinga może przesunąć tylko jedną pozycję na każdym kroku. Ponieważ głowa nie może przesunąć więcej niż o pozycji, możemy użyć tylko tylu komórek taśmy. $2^{p(n)}$ $2^{p(n)}$

$n$ , z drugiej strony, możesz nie tylko patrzeć na każdy podzbiór, ale nie musisz ponownie wykorzystywać przestrzeni roboczej, dzięki czemu możesz pamiętać, czego nauczyłeś się o każdym z nich indywidualnie. Wygląda na to, że powinien być mocniejszy.

Inną intuicją, dlaczego powinny się różnić, jest to, że twierdzenia dotyczące hierarchii czasu i przestrzeni mówią nam, że dopuszczenie nawet odrobinę więcej przestrzeni lub czasu ściśle zwiększa to, co można obliczyć. Twierdzenia o hierarchii pozwalają tylko porównywać z podobnymi (np. Pokazują, że PSPACE $\;\subsetneq\;$ $\;\subsetneq\;$

— David Richerby
źródło

Jeśli EXPTIME zezwala na przestrzeń wykładniczą, przypuszczam, że właściwym pytaniem jest, czy możemy powiedzieć, że prawdą jest, że EXPTIME jest właściwym podzbiorem EXPSPACE, ponieważ EXPSPACE pozwala na problemy, które można rozwiązać w czasie nadwykładniczym?

— user25876,

Jeśli to prawda, myślę, że wszystko ma dla mnie sens. Z jakiegoś powodu założyłem, że EXPTIME zabronił użycia przestrzeni wykładniczej, ale tak nie jest. Stąd moje zamieszanie.

— user25876,

Podoba mi się twój przykładowy podzbiór. IIRC poprawnie, znamy problemy, których nie można obliczyć online (a także z pełnymi informacjami), więc musisz zachować wszystkie elementy w pamięci. Mówiąc intuicyjnie.

— Raphael

@ user25876 Tak, ten sam argument, który mówi, że maszyna PSPACE może używać czasu wykładniczego, mówi, że maszyna EXPSPACE może używać czasu podwójnie wykładniczego (tj. ).

2^{2^{p o l y} (n)}

$2^{2^\mathrm{poly}(n)}$

— David Richerby

@DavidRicherby Przyjmuję twoją odpowiedź. Czy znasz jakieś publikacje BTW omawiające techniczne bariery dla udowodnienia lub obalenia PSPACE jako właściwego podzbioru EXPTIME? Jestem teraz bardzo ciekawy.

— user25876,

$\neq$ $\neq$

— Yuval Filmus
źródło