Jak możemy wyrazić „

1. Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?$P=PSPACE$
2. Który poziom hierarchii arytmetycznej zawiera tę formułę (i jaki jest obecnie znany minimalny poziom hierarchii, która ją zawiera)?

W celach informacyjnych zobacz ten post na blogu autorstwa Lipton .

Po pierwsze, chcę skierować komentarze do pytania, w którym zasugerowano, że wyraża się „fałsz” $P = PSPACE$ponieważ stwierdzenie jest fałszywe. Chociaż może to być dobry żart, myślenie w ten sposób jest bardzo szkodliwe. Kiedy pytamy, jak wyrazić określone zdanie w określonym systemie formalnym, nie mówimy o wartościach prawdy. Gdyby tak było, to kiedy ktoś zapytał „Jak zapisać fakt, że istnieje nieskończenie wiele liczb pierwszych?” moglibyśmy odpowiedzieć „3 + 3 = 6”, ale to na pewno nie zadziała. Z tego samego powodu „fałsz” nie jest prawidłową odpowiedzią na „jak zapisać”$P = PSPACE$? ". Myślę, że Frege i Russell starali się nas nauczyć tej lekcji. Ok, teraz odpowiedź.

Pokażę, jak wyrazić $PSPACE \subseteq P$, drugi kierunek jest podobny, a następnie można je połączyć w spójkę, aby uzyskać $PSPACE = P$. W każdym razie do celów może być wystarczające wyrażenie$PSPACE \subseteq P$, w zależności od tego, co robisz.

Wykorzystanie technik podobnych do tych w konstrukcji predykatu Kleene$T$, możemy skonstruować ograniczoną formułę kwantyfikatora $accept_{space}(k, m, n)$ (który w ten sposób rezyduje w $\Sigma^0_0 = \Pi^0_0$) mówiąc „kiedy uruchomimy maszynę zakodowaną przez $k$ i ograniczył wykorzystanie miejsca do $|n|^m$, urządzenie akceptuje dane wejściowe $n$„Tutaj $|n|$ jest długością $n$. Nieformalny sposób dostrzeżenia istnienia takich formuł jest następujący: dany$k$, $m$, i $n$ możemy obliczyć prymitywną rekurencyjną zależną od tego, ile czasu i przestrzeni będziemy potrzebować (tj. co najwyżej $|n|^m$ przestrzeń i co najwyżej $2^{|n|^m}$czas). Następnie po prostu przeszukujemy wszystkie możliwe ślady wykonania, które mieszczą się w obliczonych granicach - takie wyszukiwanie jest raczej nieefektywne, ale jest prymitywne rekurencyjne i dlatego możemy wyrazić je jako formułę ograniczoną.

Istnieje podobna formuła $accept_{time}(k, m, n)$ w którym obowiązuje czas wykonywania $|n|^m$.

Rozważmy teraz wzór:

$$\forall k, m . \exists k', m' . \forall n . accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).$$ Mówi to dla każdej maszyny $k$ który zajmuje co najwyżej miejsce $|n|^m$ jest maszyna $k'$ który korzysta w większości przypadków $|n|^{m'}$ tak, że obie maszyny akceptują dokładnie to samo $n$„s. Innymi słowy, formuła mówi$PSPACE \subseteq P$. Ta formuła to$\Pi^0_3$.

Możemy to poprawić, jeśli zamiast tego chcemy wyrazić zdanie „$TQBF$is in polytime ”, co powinno wystarczyć dla większości aplikacji, ponieważ TQBF jest ukończony PSPACE, a więc bycie w czasie polytime jest równoważne z$PSPACE \subseteq P$. Pozwolić$k_0$ być (kod) maszyną, która rozpoznaje TQBF w przestrzeni $|n|^{m_0}$. Następnie "$TQBF \in P$„można wyrazić jako

$$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$$ Ta formuła jest po prostu $\Sigma^0_2$. Gdybym był teoretykiem złożoności, wiedziałbym, czy da się zrobić jeszcze lepiej (ale wątpię).

Andrej już to wyjaśnił $P=\mathit{PSPACE}$ można zapisać jako $\Sigma^0_2$-zdanie. Pozwól mi wspomnieć, że ta klasyfikacja jest optymalna w tym sensie, że jeśli instrukcja jest równoważna do$\Pi^0_2$- to fakt ten nie relatywizuje. Dokładniej, zestaw wyroczni$A$ takie, że $P^A=\mathit{PSPACE}^A$ jest definiowany przez $\Sigma^0_2$-formula z bezpłatną zmienną drugiego rzędu $A$, ale nie jest to możliwe do zdefiniowania $\Pi^0_2$-formuła. Argument jest przedstawiony (dla$P=\mathit{NP}$, ale działa tak samo dla $\mathit{PSPACE}$) w komentarzach na stronie /mathpro/57348 . (W rzeczywistości można wykazać, opracowując ideę, że zestaw jest$\Sigma^0_2$-kompletne w odpowiednim znaczeniu).

EDYCJA: Dowód topologiczny podany w powiązanym komentarzu jest krótki, ale może wydawać się trudny. Oto argument wymuszania bezpośredniego.

$P^A\ne\mathit{PSPACE}^A$ można zapisać jako $\Pi^0_2$-formula postaci $\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$, gdzie $\theta$ jest $\Delta^0_0$. Załóżmy, że to sprzeczność$P^A=\mathit{PSPACE}^A$ jest również równoważne z $\Pi^0_2$-formuła $\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$. Napraw wyrocznie$B$, $C$ takie, że $P^B\ne\mathit{PSPACE}^B$ i $P^C=\mathit{PSPACE}^C$.

Od $\phi(B)$, tam istnieje $y_0$ takie, że $\theta(B,0,y_0)$. Jednak,$\theta$ jest ograniczoną formułą, stąd ocena wartości prawdy $\theta(B,0,y_0)$używa tylko skończonej części wyroczni. Zatem istnieje część skończona$b_0$ z $B$ takie, że $\theta(A,0,y_0)$ za każdą wyrocznię $A$ rozsuwalny $b_0$.

Pozwolić $C[b_0]$ oznacz wyrocznię, która się rozciąga $b_0$i zgadza się z $C$ gdzie $b_0$jest niezdefiniowany. Od$P^A$ i $\mathit{PSPACE}^A$ nie ma na nas wpływu skończona zmiana wyroczni, którą mamy $\psi(C[b_0])$. Istnieje ten sam argument, co powyżej$z_0$ i część skończona $c_0$ z $C[b_0]$ takie, że $\eta(A,0,z_0)$ dla każdego $A$ rozsuwalny $c_0$. Możemy to założyć$c_0$ rozszerza się $b_0$.

Kontynuując w ten sam sposób, konstruujemy nieskończone sekwencje liczb $y_0,y_1,y_2,\dots$, $z_0,z_1,z_2,\dots$i skończone częściowe wyrocznie $b_0\subseteq c_0\subseteq b_1\subseteq c_1\subseteq b_2\subseteq\cdots$ takie, że

1. $\theta(A,n,y_n)$ za każdą wyrocznię $A$ rozsuwalny $b_n$,

2. $\eta(A,n,z_n)$ za każdą wyrocznię $A$ rozsuwalny $c_n$.

Teraz pozwól $A$ bądź wyrocznią, która rozciąga wszystko $b_n$ i $c_n$. Zatem 1 i 2 implikują to$\phi(A)$ i $\psi(A)$ jednocześnie utrzymują, co jest sprzeczne z założeniem, że są one wzajemnie uzupełnieniem.