Czy problemy związane z są z natury mniej podatne na rozwiązanie niż problemy z ?

Obecnie rozwiązanie $NP$ pełnego NP lub $PSPACE$ jest niewykonalne w ogólnym przypadku dużych nakładów. Jednak oba można rozwiązać w czasie wykładniczym i przestrzeni wielomianowej.

Skoro nie jesteśmy w stanie zbudować niedeterministycznych lub „szczęśliwych” komputerów, czy ma to dla nas jakąkolwiek różnicę, jeśli problemem jest $NP$ lub $PSPACE$ -kompletny?

To bardzo miłe pytanie, o którym wiele myślałem: czy fakt, że problemem jest czy wpływa na złożoność problemu w najgorszym przypadku? $NP$$PSPACE$Co dziwniejsze, czy takie rozróżnienie rzeczywiście wpływa na złożoność problemu w „typowym przypadku” w praktyce?

Intuicja mówi, że problem z jest trudniejszy niż z , bez względu na to, jaką miarę złożoności stosujesz. Ale sytuacja jest subtelna. Może być na przykład, że (formułki logiczne, kwantyfikowany kanoniczny problem z ) występuje w podwykonawczym czasie, i tylko wtedy, gdy (Zadowalający, kanoniczny problem z niepełnym ) jest w podwykładniczym czasie. (Jeden kierunek jest oczywiste!; Drugi kierunek będzie głównym wynik) Jeśli to prawda, to może od „Chcę tylko, aby rozwiązać ten problem” punktu widzenia, to nie jest wielka sprawa, czy problem jest -Complete lub$PSPACE$$NP$$QBF$$PSPACE$$SAT$$NP$$PSPACE$$NP$-complete: tak czy inaczej, algorytm subwykładniczy dla jednego implikuje algorytm subwykładniczy dla drugiego.

Pozwólcie, że będę orędownikiem diabła, i dam wam przykład, w którym jeden problem okazuje się „trudniejszy” niż drugi, ale okazuje się „łatwiejszy do rozwiązania” niż drugi.

Niech będzie logiczną formułą dla zmiennych, gdzie jest parzyste. Załóżmy, że masz wybór między dwiema formułami, które chcesz zdecydować:$F(x_1,\ldots,x_{n})$$n$$n$

$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$ .

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

(To znaczy, w , kwantyfikatory zmieniają się).$\Phi_2$

Który z nich jest łatwiejszy do rozwiązania? Formuły typu , czy formuły typu ?$\Phi_1$$\Phi_2$

Można by pomyśleć, że oczywistym wyborem jest , ponieważ decyzja jest tylko , natomiast to problem z . Ale w rzeczywistości, według naszych najbardziej znanych algorytmów, jest łatwiejszym problemem. Nie mamy pojęcia, jak rozwiązać dla ogólnego w mniej niż krokach. (Gdybyśmy mogli to zrobić, mielibyśmy nowe dolne granice formuły!) Ale można łatwo rozwiązać dla dowolnego w losowym czasie , używając losowego wyszukiwania drzewa gry! Dla odniesienia, patrz Rozdział 2, Rozdział 2.1, w Motwani i Raghavan.$\Phi_1$$NP$$\Phi_2$$PSPACE$$\Phi_2$$\Phi_1$$F$$2^n$$\Phi_2$$F$$O(2^{.793 n})$

Intuicja polega na tym, że dodanie uniwersalnych kwantyfikatorów faktycznie ogranicza problem , czyniąc go łatwiejszym do rozwiązania niż trudniejszym. Algorytm wyszukiwania drzewa gry opiera się w dużej mierze na naprzemiennych kwantyfikatorach i nie może obsłużyć arbitralnych kwantyfikacji. Nadal jednak chodzi o to, że problemy mogą czasem stać się „prostsze” pod jedną miarą złożoności, nawet jeśli mogą wyglądać „trudniej” pod inną miarą.

Ma to znaczenie, ponieważ stawką jest coś więcej niż to, czy możemy znaleźć rozwiązania. Interesujące jest również to, czy możemy zweryfikować rozwiązania. Można wyróżnić inne rozróżnienia jakościowe między trudnością problemów, ale w przypadku NP w porównaniu z większymi klasami złożoności byłbym tym, który uznałbym za najważniejszy.

W przypadku problemów decyzyjnych - problemów, dla których każda instancja ma odpowiedź „ TAK ” lub „ NIE ” - NP jest właśnie klasą problemów, dla których możemy skutecznie zweryfikować rzekomy dowód, że dana instancja jest instancją „ TAK ”, deterministycznie, jeżeli przedstawiono nam jeden. Na przykład, jeśli masz zadowalające przypisanie zmiennych dla instancji 3-SAT, to przypisanie pozwala skutecznie udowodnić, że instancja jest zadowalająca. Takie satysfakcjonujące zadanie może być trudne do znalezienia, ale gdy już je masz, możesz łatwo udowodnić innym, że instancja jest zadowalająca, po prostu przez zweryfikowanie znalezionego rozwiązania.

Podobnie w przypadku koNP istnieją skutecznie sprawdzalne dowody dla przypadków „ NIE ”; a w przypadku problemów z NP  ∩  coNP możesz zrobić jedno i drugie. Ale w przypadku problemów związanych z PSPACE nie ma takich procedur - chyba że możesz udowodnić dość spektakularne równości klas złożoności.

Nie wiemy, jak budować trudne problemy ze średnią liczbą przypadków na podstawie (najgorszego przypadku) problemów NP-zupełnych, ale możemy to zrobić dla PSPACE (patrz Köbler i Schuler (1998) ), aby stworzyć problemy nawet przy jednolitym rozkładzie, które nie mogą być rozwiązany na większości danych wejściowych, chyba że cały PSPACE jest łatwy do obliczenia.

Od strony praktycznej ważne jest, aby pamiętać, że kompletność NP nie stanowi bariery dla wielu problemów w praktyce. Bliźniacze narzędzia solverów SAT i CPLEX (do programowania liniowego liczb całkowitych) są wystarczająco mocne i wystarczająco dobrze zaprojektowane, aby często można było rozwiązać duże przypadki problemów z NP-kompletnością albo przez kadrowanie problemu jako odpowiedniej ILP, albo przez redukcję do SAT.

Nie znam podobnie dobrze zaprojektowanych rozwiązań dla problemów w PSPACE.

Możesz pomyśleć o tym w ten sposób: czy problem matematyczny ma dowód, który jest czytelny dla człowieka, czy też z natury wymaga „dowodu komputerowego”. Przykłady: czy pozycja początkowa warcabów jest remisem? (Odpowiedź: tak.) Czy pozycja wyjściowa szachów jest zwycięstwem białych? (Odpowiedź: nieznana, ale większość gradmasterów uważa, że ​​to remis.)

Dowód, że pozycja początkowa warcabów jest remisem, ostatecznie wymaga zaakceptowania, że ​​komputer naprawdę dokładnie zweryfikował wiele specjalnych przypadków. Jeśli kiedykolwiek istnieje dowód na szachy, prawdopodobnie czytelnicy będą musieli zaakceptować, że komputer poprawnie zweryfikował jeszcze więcej specjalnych przypadków. Być może nie ma krótszej metody na potwierdzenie tych twierdzeń. To są problemy w PSPACE. Jeśli problemem jest „tylko” NP, to (intuicyjnie) człowiek może trzymać cały dowód w swojej głowie. Ten człowiek może oczywiście być bardzo wyspecjalizowanym matematykiem.

Ta metafora załamie się, jeśli zostanie zbyt mocno popchnięta - dowód NP o rozmiarze prawdopodobnie nigdy nie zmieści się w głowie. Ale podstawowa idea, że ​​„świadkowie są mali”, jest jednym z powodów, dla których problemy NP-zupełne mają tak duże znaczenie przemysłowe.$n^{1000000}$

Po komentarzu Suresha wydaje się, że w praktyce istnieje duża różnica. Istnieją heurystyki, które potrafią wykorzystać strukturę praktycznych instancji SAT i uzyskać doskonałą wydajność (odnoszę się tutaj do rozwiązujących uczenie się klauzul opartych na konfliktach). Ta sama heurystyka nie powoduje podobnej poprawy wydajności w rozwiązaniach QBF.

Pojawia się również różnica między dowodem a weryfikacją. Niektóre solwery SAT (takie jak MiniSAT 1.14 i wiele innych) dają dowody. Tworzenie dowodów w obecnych rozwiązaniach QBF nie jest trywialne. (Następna wypowiedź pochodzi ze słyszenia) W konkursie QBF występują duże przypadki, w których solwery najwyraźniej dają różne wyniki. W przypadku braku solverów generujących dowody nie wiemy, który wynik jest poprawny.

Jeśli spojrzysz na praktyczne wyniki na SAT i szachach, to jest różnica - problemy z kompletnym NP są łatwiejsze do rozwiązania niż problemy z kompletnym PSPACE. Rozwiązania SAT dzisiaj mogą obsłużyć ponad tysiąc zmiennych, ale najlepszy silnik szachowy, w tym samym czasie, może obliczyć tylko mniej niż 20 ruchów.

Myślę, że dzieje się tak ze względu na strukturę problemów. Tak, jeśli tylko wyliczysz rozwiązania, rozwiązywanie SAT jest bardzo wolne. Ponieważ jednak nie ma on zmienności kwantyfikatora, ludzie odkrywają struktury we wzorze i dlatego unikają dużej ilości wyliczeń. Myślę, że Ryan Williams przeoczył ten punkt.

Przy naprzemiennym kwantyfikatorze tak, istnieją inteligentne metody przycinania, ale struktura nie jest tak bogata, jak w przypadku formuły CNF.

Pozwól mi przewidzieć przyszłość. Rozwiązanie SAT dostanie się do P, sprawdzając formułę i zasadniczo unikając wyszukiwania, podczas gdy szachy dostaną się do P, wykorzystując wyszukiwanie w drzewie gry.