Jak możemy wyrazić „

9
  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 .

Mars
źródło
1
Być może możesz użyć tego samego dowodu Liptona, używając problemu pełnego PSPACE zamiast SAT w definicji i otrzymujesz, że można wyrazić jako tj. jest to zdanie . Ale IMO to rodzaj „hacka” ... :-)ψ(x,c,y)PPSPACEx,cyψ(x,c,y)Π2
Marzio De Biasi
3
Założę się, że moje życie i cały światowy dobytek można przedstawić jako „Fałsz”. Oznacza to, że można to wyrazić nawet w logice zdań. :)
Shaull,
3
@Shaull. Pewnie. A kiedy pokażesz, że jest to poprawna reprezentacja, będziesz mógł kupić wszystkie potrzebne rzeczy. Nie protestuj, że miejsce na komentarz jest za krótkie, aby zawierać dowód.
Vijay D,
3
@VijayD - wezmę przynętę: znalazłem naprawdę wspaniały dowód, a miejsce na komentarze jest wystarczające. Ale nie podoba mi się czcionka ...
Shaull,

Odpowiedzi:

25

Po pierwsze, chcę skierować komentarze do pytania, w którym zasugerowano, że wyraża się „fałsz” P=PSPACEponieważ 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ć PSPACEP, 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żeniePSPACEP, w zależności od tego, co robisz.

Wykorzystanie technik podobnych do tych w konstrukcji predykatu KleeneT, możemy skonstruować ograniczoną formułę kwantyfikatora acceptspace(k,m,n) (który w ten sposób rezyduje w Σ00=Π00) 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: danyk, 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|mczas). 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 accepttime(k,m,n) w którym obowiązuje czas wykonywania |n|m.

Rozważmy teraz wzór:

k,m.k,m.n.acceptspace(k,m,n)accepttime(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ówiPSPACEP. Ta formuła toΠ30.

Możemy to poprawić, jeśli zamiast tego chcemy wyrazić zdanie „TQBFis 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 zPSPACEP. Pozwolićk0 być (kod) maszyną, która rozpoznaje TQBF w przestrzeni |n|m0. Następnie "TQBFP„można wyrazić jako

k,m.n.acceptspace(k0,m0,n)accepttime(k,m,n).
Ta formuła jest po prostu Σ20. Gdybym był teoretykiem złożoności, wiedziałbym, czy da się zrobić jeszcze lepiej (ale wątpię).
Andrej Bauer
źródło
twój pierwszy akapit jest prawie logiczną, tekstową formą tego: xkcd.com/169
Vijay D
21

Andrej już to wyjaśnił P=PSPACE można zapisać jako Σ20-zdanie. Pozwól mi wspomnieć, że ta klasyfikacja jest optymalna w tym sensie, że jeśli instrukcja jest równoważna doΠ20- to fakt ten nie relatywizuje. Dokładniej, zestaw wyroczniA takie, że PA=PSPACEA jest definiowany przez Σ20-formula z bezpłatną zmienną drugiego rzędu A, ale nie jest to możliwe do zdefiniowania Π20-formuła. Argument jest przedstawiony (dlaP=NP, ale działa tak samo dla PSPACE) w komentarzach na stronie /mathpro/57348 . (W rzeczywistości można wykazać, opracowując ideę, że zestaw jestΣ20-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.

PAPSPACEA można zapisać jako Π20-formula postaci ϕ(A)=xyθ(A,x,y), gdzie θ jest Δ00. Załóżmy, że to sprzecznośćPA=PSPACEA jest również równoważne z Π20-formuła ψ(A)=xzη(A,x,z). Napraw wyrocznieB, C takie, że PBPSPACEB i PC=PSPACEC.

Od ϕ(B), tam istnieje y0 takie, że θ(B,0,y0). Jednak,θ jest ograniczoną formułą, stąd ocena wartości prawdy θ(B,0,y0)używa tylko skończonej części wyroczni. Zatem istnieje część skończonab0 z B takie, że θ(A,0,y0) za każdą wyrocznię A rozsuwalny b0.

Pozwolić C[b0] oznacz wyrocznię, która się rozciąga b0i zgadza się z C gdzie b0jest niezdefiniowany. OdPA i PSPACEA nie ma na nas wpływu skończona zmiana wyroczni, którą mamy ψ(C[b0]). Istnieje ten sam argument, co powyżejz0 i część skończona c0 z C[b0] takie, że η(A,0,z0) dla każdego A rozsuwalny c0. Możemy to założyćc0 rozszerza się b0.

Kontynuując w ten sam sposób, konstruujemy nieskończone sekwencje liczb y0,y1,y2,, z0,z1,z2,i skończone częściowe wyrocznie b0c0b1c1b2 takie, że

  1. θ(A,n,yn) za każdą wyrocznię A rozsuwalny bn,

  2. η(A,n,zn) za każdą wyrocznię A rozsuwalny cn.

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

Emil Jeřábek
źródło
3
Smutne, że taka miła odpowiedź jest na pytanie, które jest już zamknięte ...
arnab