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

66

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?

Alex ten Brink
źródło

Odpowiedzi:

82

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? NPPSPACECo 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 lubPSPACENPQBFPSPACESATNPPSPACENP-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(x1,,xn)nn

Φ1=(x1)(x2)(xn1)(xn)F(x1,,xn) .

Φ2=(x1)(x2)(xn1(xn)F(x1,,xn)

(To znaczy, w , kwantyfikatory zmieniają się).Φ2

Który z nich jest łatwiejszy do rozwiązania? Formuły typu , czy formuły typu ?Φ1Φ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.Φ1NPΦ2PSPACEΦ2Φ1F2nΦ2FO(2.793n)

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

Ryan Williams
źródło
16
Ładna odpowiedź i ciekawe ujęcie.
Suresh Venkat
Przyszło mi do głowy, że powyższe jest całkiem dobrym przykładem tego, co rozumiemy przez „drobnoziarnistą złożoność” (program z jesieni 2015 r. W Instytucie Simonsa). Jedną z kluczowych idei jest to, że teoria złożoności może wyglądać zupełnie inaczej, gdy zamiast próbować znaleźć dla każdego problemu (potencjalnie dziwaczny) model obliczeniowy, dla którego problem ten jest „kompletny”, wystarczy skupić się na zrozumieniu najlepszego możliwego czasu działania wykładnik problemu.
Ryan Williams
37

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.

Niel de Beaudrap
źródło
Myślę, że pytanie dotyczy wersji „optymalizacyjnej” problemów NP-complete i PSPACE-complete. Na przykład, czy jest jakaś różnica (pod względem złożoności) między znalezieniem rozwiązania dla SAT a dla QBF? Mówiąc bardziej ogólnie, czy istnieje charakterystyka problemów związanych z optymalizacją, których wersja decyzyjna jest NP-complete lub PSPACE-complete?
Lamine,
@Lamin: Nie wyczuwam rozróżnienia, które wprowadzasz w pytaniu (przynajmniej między samą decyzją a pełną optymalizacją). Być może masz na myśli, że pytający jest zainteresowany jedynie pytaniem o zasoby potrzebne do znalezienia tej odpowiedzi i nie jest zainteresowany innymi miernikami trudności problemu, w którym to przypadku zgadzam się, że moja odpowiedź nie odpowiada na to pytanie. W każdym razie powyżej znajduje się moja odpowiedź na pytanie w obecnej formie.
Niel de Beaudrap,
5
Bardzo miła odpowiedź.
Dave Clarke
Zdolność do sprawnej weryfikacji nie pomaga w obliczeniu rozwiązania (chyba że P = NP). NP i co-NP umożliwiają atakowanie problemu poprzez odgadnięcie i weryfikację. Takie podejście jest łatwe do wdrożenia, a może nawet być bardziej wydajne, ale w najgorszym przypadku nie pomaga.
András Salamon,
@ András: true - dlatego podkreślam, że znalezienie rozwiązań nie jest jedyną ważną rzeczą we wstępie do mojej odpowiedzi.
Niel de Beaudrap,
36

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.

Lance Fortnow
źródło
20

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.

Suresh Venkat
źródło
11
Organizowany jest coroczny konkurs mający na celu ulepszenie solverów QBF . Nie korzystałem z nich zbyt często.
Radu GRIGore
7

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

Aaron Sterling
źródło
Czy można również argumentować, że problemy z kompletnym koNP mają ten problem (czasem) wymagający „dowodu komputerowego”?
Philip White
@Philip White: Nie sądzę, że jest tak samo. Powiedz „szachy remis” jest w CoNP. Aby powiedzieć „nie”, muszę jedynie zademonstrować pojedynczą linię wymuszającą, którą można łatwo zweryfikować. Oczekujemy jednak, że nawet jeśli taka linia istnieje, prawdopodobnie bardzo trudno będzie udowodnić, że rzeczywiście „wymusza”. Problem nie daje więc gwarancji prostoty, jeśli można go rozwiązać w określonym kierunku. „Szachy to losowanie” prawdopodobnie z natury wymaga komputera, aby udowodnić, czy jest to prawda, czy fałsz.
Aaron Sterling
5

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.

Vijay D.
źródło
0

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.

Zirui Wang
źródło