Jak trudna jest dokładna symulacja algorytmów i powiązana z nią operacja na klasach złożoności

Zwiastun

Ponieważ problem jest długotrwały, tutaj jest szczególny przypadek, który oddaje jego istotę.

Problem: Niech A będzie algorytmem detrministycznym dla 3-SAT. Czy problem polega na całkowitej symulacji algorytmu A (na każdym wystąpieniu problemu). P-Space trudne?

(Dokładniej, czy istnieją powody, by sądzić, że to zadanie jest trudne dla P-Space, robi coś w tym kierunku ze standardowych przypuszczeń CC i ma nadzieję udowodnić, że to zadanie jest trudne dla X dla jakiejś klasy złożoności X, o której zakłada się, że być powyżej NP.)

Powiązane pytania : are-pspace-complete-problems-inherently-less-tractable-than-np-complete-problems ;

ZAKTUALIZOWANA AKTUALIZACJA : Istnieją różne interpretacje dla „Całkowicie symulującej A”. W zależności od interpretacji mogą istnieć różne interesujące odpowiedzi. (Również Ryan Williams zaproponował interpretację symulacji niedeterministycznego algorytmu.) Aby w pewien sposób powiązać problem decyzyjny z zadaniem obliczeniowym „Całkowicie symulować A”, Joe Fitzsimons znalazł algorytm A, dla którego ten związany z nim problem decyzyjny wciąż występuje w NP . Jeśli „całkowicie symulować” odnosi się do możliwości wypisania całego rejestru komputera na danym etapie $i$ to w przypadku algorytmu Joe wydaje się, że $P^{NP}$ jest potrzebne. W przypadku tej wersji (tak myślę, ale nie jestem pewien) odpowiedź Ryana szkicuje $P^{NP}$argument o twardości. Joe zauważył, że jeśli od was wymaga się dostarczenia całych rejestrów (co nie jest już problemem decyzyjnym), nie jest zaskakujące, że trzeba przyspieszyć, a klasy złożoności nie są takie same.

W każdym razie, jeśli wymaga wyjścia stan rejestrów w wyznaczonym punkcie $i$ wtedy Odpowiedzi Ruan i Joe sugeruje (ale znowu, nie jestem pewien o tym), że $NP^+$ jest zasadniczo $P^{NP}$ . Można spaculate że tą interpretacją operację umieszcza się jeden krok w wielomian hiearachy, a $PH^+ =PH$ .

W każdym razie na podstawie tych interpretacji odpowiedź na moje zwiastunowe pytanie brzmi NIE .

Miałem na myśli bardziej drastyczną interpretację „całkowicie symulującego algorytm A”. (Ale może interpretacja Joe i Ryan jest bardziej interesująca.) Moja interpretacja „całkowicie symulowanie algorytm A” jest to, że outout stanu rejestrów na każdym kroku . W szczególności, jeśli algorytm nie jest wielomianowy, dane wyjściowe również nie są wielomianowe. Przy tej drastycznej interpretacji zastanawiałem się, czy powinniśmy wierzyć, że dla każdego algorytmu A C A jest trudne dla P-SPACE i co możemy udowodnić.$i$$C_A$

Motywacja:

To pytanie było motywowane wykładem Paula Goldberga ( slajdy , wideo , papier ) opisującym artykuł z Papadimitriou i Savani. Wykazali, że przestrzeń P jest kompletna, aby znaleźć równowagę obliczoną przez algorytm Lemke-Howsona. Problem znalezienia punktu równowagi jest tylko PPAD. Ta luka jest dość zdumiewająca, a podobne wyniki opisano już w dobrze znanym artykule Papadimitriu: Złożoność argumentu parzystości i inne nieefektywne dowody istnienia (1991) . (Wiadomo, że problemy z kompletnym PPAD nie mogą być nawet trudne NP (chyba że zdarzają się straszne rzeczy, więc jest to znacznie mniej w świecie złożoności w porównaniu z przestrzenią P).

O co chodzi w tym pytaniu

Moje pytanie dotyczy podobnych luk w nawet starszych i bardziej klasycznych problemach ze złożonością obliczeniową. (Może to już jest znane).

Biorąc pod uwagę problem obliczeniowy, możemy rozróżnić trzy kwestie

a) Rozwiąż problem algorytmicznie

b) Osiągnij to samo rozwiązanie, co określony algorytm A

c) Symulować cały algorytm A

Oczywiście c) jest co najmniej tak samo twardy jak b) co najmniej tak samo twardy jak a). Powyższe wyniki pokazują lukę między trudnością obliczeniową zadań a) ib) dla problemu obliczania równowagi. Chcielibyśmy zrozumieć sytuację (a przede wszystkim lukę między a) ic)) w przypadku innych problemów obliczeniowych.

Pytanie:

Podstawowa forma pytania z przykładem

Zaczynamy od problemu obliczeniowego, problemu X

Przykładem może być

Problem X: Rozwiąż instancję SAT za pomocą n zmiennych

określamy również

Odp .: algorytm, który wykonuje Problem X.

i stawiamy nowy problem

Problem Y: Dokładnie symuluj algorytm A

i interesuje nas trudność obliczeniowa problemu Y. Chcemy zrozumieć klasę takich problemów Y dla wszystkich algorytmów A, które rozwiązują pierwotny problem X. W szczególności chcemy wiedzieć, jak łatwy może być problem Y (lub jak trudny musi być be) jeśli możemy wybrać algorytm A do woli.

Proponowana operacja na klasach złożoności

Zacznij od klasy złożoności która jest opisana przez jakieś zadanie obliczeniowe. Biorąc pod uwagę algorytm A, aby wykonać każde wystąpienie tego zadania obliczeniowego, należy rozważyć nową klasę złożoności C A , która jest opisana przez obliczeniowej zadania zupełnie symulujący A . Następnie możemy (mam nadzieję) zdefiniować „ideał” klas złożoności$C$$C_A$$A$

dla wszystkich algorytmów A}.$C^+ = \{C_A:$

Jeśli pozwolimy opisać wszystko, co komputer cyfrowy może zrobić w czasie wielomianowym (więc nie chcę ograniczać uwagi np. Do problemów decyzyjnych), wówczas P + jest idealnym rozwiązaniem dla samego $P$$P^+$$P$

Wreszcie moje pytania

Moje pytania to:

1) Czy definicja ma sens (w szerokim znaczeniu tego słowa)? Czy to jest dobrze znane, czy to samo (lub podobne) do jakiejś dobrze znanej rzeczy. (Moje sformułowanie było nieformalne, a zwłaszcza gdy przechodzimy od konkretnych problemów, takich jak SAT, do klasy złożoności, takiej jak NP, musimy martwić się o różne rzeczy, które zaniedbałem.)

Następne dwa pytania zakładają, że definicja może mieć sens lub być uratowana, aby miała sens.

2) Załóżmy, że wyposażamy się we wszystkie standardowe przypuszczenia dotyczące zgodności obliczeniowej. Czy możemy powiedzieć, czym powinien być dla niektórych znanych klas złożoności. (Np. C = N P , C = P-space, ..)? Edycja: Kilka osób wskazać, że P S P C E + = P S P C e . Więc> możemy zamiast tego zapytać, co to jest ( P N P ) + ? jest P H + = P H ?$C^+$$C=NP$$C$$PSPACE^+=PSPACE$$(P^{NP})^+$$PH^+=PH$

Czy możemy zgadnąć, jakie są klasy współzależności , aby C + był ideałem rozpiętym przez C ?$C$$C^+$$C$

Pytanie o to, jak łatwe może być zadanie obliczeniowe polegające na symulacji algorytmu A dla 3-SAT (kiedy możemy wybrać algorytm, aby uczynić go tak łatwym, jak to możliwe) jest interesującym szczególnym przypadkiem.

3) Czy istnieje nadzieja, że ​​uda się coś udowodnić w tej operacji?

Oczywiście, jeśli udowodnisz, że wszystkie klasy złożoności w są twarde w przestrzeni P , pokaże to, że P = N P implikuje P = P S P A C E , co (myślę) byłoby ogromnym i wysoce nieoczekiwanym wynikiem . Ale jeśli wykazują, że wszystkie klasy złożoności N P + są trudne do Somthing powiedzenia w trzecim poziomie wielomianu Hieararchy (np Δ P 3 ) to oznaczałoby tylko rzeczy, które już wiemy rzeczy, które wynikają z faktu, że P = N P powoduje załamanie PH.$NP^+$$P=NP$$P=PSPACE$$NP^+$$\Delta_3^{\bf P}$$P=NP$

Problem: Niech A będzie algorytmem deterministycznym dla 3-SAT. Czy problem całkowitej symulacji algorytmu A (w każdym przypadku problemu) P-Space jest trudny?

Nie rozumiem stwierdzenia tego problemu. Ale myślę, że istnieje naturalny sposób sformalizowania twojego bardziej ogólnego pytania, które może rzucić na to trochę światła. Może zupełnie nie rozumiem tego, ale mam nadzieję, że wciąż znajdziesz tu coś interesującego do przeczytania.

1) Czy definicja ma sens (w szerokim znaczeniu tego słowa)? Czy to jest dobrze znane, czy to samo (lub podobne) do jakiejś dobrze znanej rzeczy. (Moje sformułowanie było nieformalne, a zwłaszcza gdy przechodzimy od konkretnych problemów, takich jak SAT, do klasy złożoności, takiej jak NP, musimy martwić się o różne rzeczy, które zaniedbałem.)

Jednym ze sposobów na zrozumienie zadania ,$Y$ jakim jest dokładnie symulacja algorytmu Y, jest następujący. Dla uproszczenia naprawmy model, który będzie maszyną Turinga z jedną taśmą; to, co powiem, może dotyczyć każdego typowego modelu obliczeniowego.

Dla każdego algorytmu i wejścia x możemy zdefiniować jego historię obliczeń H Y ( x , i , j ) : Podane liczby całkowite i oraz j mieszczą się w zakresie od 0 do czasu działania Y , H Y ( x , i , j ) równa się zawartość j- tej komórki taśmy maszyny Turinga Y na wejściu x w kroku czasowym i . (A jeśli głowica taśmy czyta $Y$$x$ $H_Y(x,i,j)$$i$$j$$0$$Y$$H_Y(x,i,j)$$j$$Y$$x$$i$$j$komórka w tym kroku, również to uwzględniające stan maszyny.) Oczywiście historie obliczeń pojawiają się cały czas w teorii złożoności.$i$

Teraz można argumentować, że dowolny algorytm decydujący o języku

$C_Y = \{(x,i,j,\sigma)~|~H_Y(x,i,j)=\sigma\}$

(lub symulowania funkcji na wszystkich wejściach) rozwiązuje zadanie dokładnie algorytm symulacji Y , ponieważ ma możliwość drukowania każdą małą część wszystkich możliwych obliczeń algorytmu Y . Oczywiście, mając wyrocznię dla C Y, można by przeprowadzić symulację Y krok po kroku .$H_Y$$Y$$Y$$C_Y$$Y$

2) Załóżmy, że wyposażamy się we wszystkie standardowe przypuszczenia dotyczące złożoności obliczeniowej. Czy możemy powiedzieć, czym powinien być C ++ dla niektórych znanych klas złożoności. (Np. C = NP, C = P-space, ..)? Czy możemy zgadnąć, jakie są klasy złożoności C, aby C + był idealną rozpiętością C?

To jest nadal interesujące pytanie w ramach powyższej propozycji. W deterministycznych klasach czasu nic się nie zmienia. jest po prostu P : możemy zdecydować C Y w polytime dla każdego algorytmu polytime. Podobnie E X P + = e x P . Również P S P C E + nadal P S P C e . Dla niedeterministycznych klas złożoności czasu sytuacja staje się bardziej interesująca. W takim przypadku algorytm Y może mieć wiele historii obliczeń, więc$P^+$$P$$C_Y$$EXP^+ = EXP$$PSPACE^+$$PSPACE$$Y$ nie jest już dobrze zdefiniowany. Jednak nadal chcemy wydrukowaćtrochęhistorii obliczeń, więc nasza „dokładna symulacja” musiałaby wyodrębnić konkretną niedeterministyczną historię obliczeń, a następnie wydrukować jej wartości. W przypadkualgorytmu N P Y można powiedzieć, że C Y ∈ P N P : możemy użyćwyroczni N P do binarnego wyszukiwania „pierwszej” historii akceptacji obliczeń (w porządku lex), a następnie, gdy ją uzyskamy, wydrukuj odpowiednie bity. W przypadkualgorytmu N E X P Y można powiedzieć C Y$H_Y$$NP$$Y$$C_Y \in P^{NP}$$NP$$NEXP$$Y$ , z podobnych powodów.$C_Y \in EXP^{NP}$

Czy możemy umieścić w mniejszej klasie? Nie wiem Zauważ, że nie możemy po prostu przedefiniować$NP^+$

{ ( x , i , j , σ ) | istnieje H Y taki, że H Y ( x , i , j ) = σ }$C_Y =$$(x,i,j,\sigma)~|~$$H_Y$$H_Y(x,i,j)=\sigma$

próbujemy umieścić w N P , ponieważ potrzebujemy, aby ciąg historii był taki sam dla wszystkich poczwórnych z udziałem x , aby „dokładnie symulować algorytm Y ”.$C_Y$$NP$$x$$Y$

W każdym razie ten problem niemożności „wydrukowania świadka” do obliczeń bez przejścia do E X P N P pojawia się w niektórych sytuacjach, takich jak złożoność obwodu. Jeżeli N E X P zawiera obwody wielomianowych wielkości, to jest to również przypadek, C, Y ∈ P / p O l y dla każdego niedeterministycznych 2 n k czasu Y ? Impagliazzo, Kabanets i Wigderson$NEXP$$EXP^{NP}$$NEXP$$C_Y \in P/poly$$2^{n^k}$$Y$odpowiedział na to pytanie twierdząco w 2001 r. Ich dowód jest niezwykle interesujący, przywołując narzędzia z derandomizacji i diagonalizacji (dlaczego derandomizacja byłaby konieczna do takiego wyniku?) i okazuje się być bardzo przydatnym twierdzeniem do udowodnienia dolnych granic obwodu dla Funkcje $NEXP$

Czy istnieje nadzieja, że ​​uda się coś udowodnić w tej operacji?

Może ... to zależy od tego, czy jesteś zadowolony z powyższej formalizacji swojego pytania. Dla deterministycznej 3-SAT algorytm , to, że powyższy dokładny symulacji Y problemu byłoby P N P ( 1 ) -hard, gdzie P N P ( 1 ) jest wielomianem razem z jednym zapytania do N P . (Irytująca składnia StackExchange wymaga napisania (1) zamiast alternatywy. Wcześniej powiedziałem, że C Y powinien być P N P- twardy, ale nie jestem pewien szczegółów: możesz zobaczyć, jak uogólnić poniższe.)$Y$$Y$$P^{NP(1)}$$P^{NP(1)}$$NP$$C_Y$$P^{NP}$

Podajemy polytime wiele -on redukcji z każdym do C Y . Biorąc pod uwagę takie l , niech M być maszyną do rozpoznawania L , który ma jeden N P zapytania. WLOG, to zapytanie jest formułą SAT. Również WLOG, kwerenda SAT może zostać „przełożona” do ostatniego etapu obliczeń, w tym sensie: istnieje algorytm wielomianowy A ( x ), który wypisuje formułę F i bit b , tak że dla wszystkich x ,$L \in P^{NP(1)}$$C_Y$$L$$M$$L$$NP$$A(x)$$F$$b$$x$

akceptuje iff A ( x ) = ( F , b ) tak, że ( S A T ( F ) XOR b ) = 1.$M(x)$$A(x)=(F,b)$$SAT(F)$$b$

( może odrzucić iff F jest zadowalające lub może zaakceptować; bit b przechwytuje to.)$M$$F$$b$

Dla uproszczenia powiedzmy, że gdy zakończy obliczenia, przesuwa swoją taśmę do komórki 1, zapisuje „akceptuj” lub „odrzucaj” w tej komórce i zapętla na zawsze. Następnie pytanie, czy ( F , T , 1 , a c c e p t ) ∈ C Y dla wystarczająco dużego T powie nam, czy F jest akceptowane. (W ogóle, po prostu trzeba, że jest to skuteczne, aby obliczyć instancji y o C Y , który nam powie.) Uwaga to już pokazuje, że C Y jest zarówno N P -hard i$Y$$(F,T,1,accept) \in C_Y$$T$$F$$y$$C_Y$$C_Y$$NP$ twardy; to ostatnie jest prawdziwe, ponieważ ( F , T , 1 , r e j e c t ) ∈ C Y iff F niejestzadowalający.$coNP$$(F,T,1,reject) \in C_Y$$F$

Ostateczna redukcja z do C Y jest następująca: biorąc x , uruchom A ( x ) otrzymując ( F , b ) . Jeśli b = 0, wówczas wyjście ( F , T , 1 , a c c e p t ) , w przeciwnym razie, jeśli b = 1 wyjście ( F , T , 1 , r e j e c $L$$C_Y$$x$$A(x)$$(F,b)$$b=0$$(F,T,1,accept)$$b=1$ .$(F,T,1,reject)$

Dla każdego wytwarzamy (w czasie wielomianowym) ą y takie, że M ( X ) przyjmuje IFF y ∈ C Y .$x$$y$$M(x)$$y \in C_Y$

(Podziękowania dla Joe za domaganie się bycia jaśniejszym w tej części.)

Ale nie widzę (na przykład), jak uzyskać twardość. Aby zredukować Σ 2 -SAT do problemu, wydaje się, że musisz napisać instancję x 3-CNF SAT, która symuluje twój deterministyczny algorytm Y w nim (gdzie Y rozwiązuje Tautologie na różnych podproblemach). Ale ponieważ Y nie ma określonego limitu czasu, ten 3-CNF x może być ogromny, więc niekoniecznie dostajesz redukcję czasu wielomianowego. Chyba że coś mi umknie.$\Sigma_2 P$$\Sigma_2$$x$$Y$$Y$$Y$$x$

I initially posted an incorrect answer, so hopefully this is an improvement.

I'm going to start out by considering the 3SAT example. In your comment on Ryan's answer you say

Ciekawe, jak trudno jest symulować deterministyczny algorytm Y dla 3-SAT. A pytanie brzmi, czy niezależnie od tego, co to jest Y, jest to trudna do spacja.

Odpowiedź na to jest taka, że ​​nie jest trudna dla PSPACE przynajmniej dla części Y, zakładając, że ACE PSPACE NP , ale istnieją inne algorytmy, dla których jest trudna dla PSPACE. Pokazanie tego drugiego jest trywialne: po prostu konstruujemy algorytm, który interpretuje ciąg bitów reprezentujący formułę 3SAT zamiast tego jako problem TQBF, który następnie rozwiązuje przed rozwiązaniem instancji 3SAT. Oczywiście w tym przypadku nie ma nic specjalnego w TQBF, więc algorytm może być utrudniony do symulacji. Powinniśmy więc dbać tylko o dolne granice symulacji dowolnego algorytmu dla danego problemu, a nie o konkretny algorytm.$\neq$

With that in mind, we construct the following algorithm to solve 3SAT:

Take a register of $n$ bits (initially all set to 0) to contain a trial solution, together with a register containing the 3SAT instance, a counter register of size $\lceil\log_2 (c + 1)\rceil$ initially set to 1 and and two flag bits (call these the fail flag and the accept flag). Here $c$ is the number of clauses. The algorithm then proceeds as follows:

• If the value of the clause counter $k$ is less than or equal to $c$, and the trial solution is not $111......1$, check whether clause $k$ is satisfied. If not set the fail bit. Increment the counter.
• If the value of the clause counter $k$ is less than or equal to $c$, and the trial solution is $111......1$, check whether clause $k$ is satisfied. If it is not, set the fail flag. Increment the counter.
• If $k$ exceeds $c$, and the trial solution is not $111......1$, check if the fail flag is set. If so then increment the trial solution, reset the counter $k$ to 1, and unset the fail flag. If the fail flag was not set, set the accept flag, set the clause counter $k$ to zero, set the trial solution to zero and halt.
• If $k$ exceeds $c$, and the trial solution is $111......1$, check if the fail flag is set. If the fail flag was not set, set the accept flag. Set the clause counter $k$ to zero, set the trial solution to zero and halt.

When the algorithm halts, the state of the accept flag tells you whether or not the 3SAT formula can be satisfied.

Now, if I want to compute the state of the algorithm at time $i$ I have an algorithm to compute this in polynomial time with a single call to an NP oracle as follows:

Note that for any $i$, assuming the accept bit has not yet been set, the state of the registers can be calculated in polynomial time, since the value of $k$ and the trial solution register $t$ are simply functions of $i$. Determining if the fail flag is set can be done in polynomial time, simply by checking whether the current state of the trial solution register satisfies all clauses less than or equal the current value of $k$. If and only if this not the case, the fail flag is set. The accept flag is set to zero.

Similarly, if the accept bit has already been set, the state of the registers can be efficiently computed, since everything is zero except the accept bit, which is set.

So the only hardness comes in determining whether the accept bit is set. This is equivalent to determining whether the given 3SAT instance has a solution less than $t$. If it does, then the accept bit must necessarily be set, and if it does not, then the accept bit must necessarily be zero. Clearly this problem is itself NP-complete.

Thus the state of the system at step $i$ can be determined by in polynomial time with a single query to an NP oracle.

Important update: Initially I had misread Ryan's formulation of exact simulation as a decission problem, and so my claim that the decission version was in NP was incorrect. Given the problem of deciding whether bit $j$ at step $i$ on input $x$ as formulated in Ryans answer, then there are 3 possibilities:

1. This bit is constant in independent of whether $F$ is satisfiable. As there are only two possible states for the system at this time (both of which can be computed in P) determining if this is the case, and if so, whether the value is equal to $\sigma$ is in P.
2. The bit is equal to $\sigma$ if $F\in SAT$, and unequal otherwise. This problem is clearly in NP, as the satisfying assignment of $F$ acts as a witness.
3. The bit is equal to $\sigma$ if $F\in UNSAT$ in which case the problem is then in coNP.

Clearly deciding which one of these three is the case can be done in polynomial time, simply by comparing the value that bit takes if $F\in SAT$ and if $F\in UNSAT$. Thus the exact simulation problem is in NP $\cup$ coNP. Thus, as Ryan's lower bound and my upper bound match, assuming both are correct, I think we have an answer: $C_Y = NP\cup coNP$.

Note that there is nothing special about 3SAT in this case, and the same could be done for any problem in NP. Further, the same trick can be used for any non-deterministic complexity class, not just NP, which seem to be the hard ones to simulate. For deterministic classes you can simply run the best algorithm and halt at step $i$. So with this in mind, full simulation of at least some deterministic algorithm for a problem is only as hard as solving the problem itself.

Very interesting thought! Here's an extended comment that was too long to post as such:

Regarding the definition in (1) as such, that is:

Start with a complexity class $C$ which is described by some computational task. Given an algorithm A to perform every instance of this computational task, consider a new complexity class $C_A$ which is described by the computational task of completly simulating $A$. Then we can (hopefully) define an "ideal" of complexity classes: $C^+ = \{C_A:$ for all algorithms $A\}$.

I believe you're going to quickly run into an issue with undecidability for non-trivial membership in $C^+$. In particular, given the description of two TMs $M$ and $M^{\prime}$, it's well-known that deciding whether they accept the same language (i.e. $L(M) \stackrel{?}{=} L(M^{\prime})$ is undecidable in general by reduction from the Halting Problem.

Further, given the description of a Turing Machine , there is always a trivial simulation: Just construct a new Turing Machine $M^*$ that calls $M$ as a subroutine (using its description), which accepts if $M$ accepts and rejects if $M$ rejects. This only costs a linear overhead. Specifically, if $M$ runs in $t(n)$ computational steps, then $M^*$ runs in $O(t(n))$ (whereby "run," I mean "simulates $M$ exactly").

This suggests to me that if there's any serious traction to be gained here, the precise way you go about making the definition of the ideal of a complexity class is going to be fairly important. In particular, if you intend to show that the ideal of, say, $NP$ is $PSPACE$-hard, you'll have to rule out the notion of a trivial, linear-time simulation of the $NP$ machines in question.

With respect to the homotopy methods described in the talk/paper and GPS's $PSPACE$-completeness result, I believe the "gap" you're witnessing between $PPAD$-completeness and $PSPACE$-hardness is due to the distinction between finding any NE (in the sense of END OF LINE) and finding a unique NE given a specific, initial configuration (in the sense of OTHER END OF LINE).