Obliczanie wszelkich informacji o Max-3SAT

O wzorze 3CNF pozwolić jest w maksymalna liczba zadowoleni klauzul jakimkolwiek wyznaczeniem . Wiadomo, że wartość Max-3SAT jest trudna do przybliżenia (z zastrzeżeniem P ≠ NP), tj. Nie ma algorytmu czasu policyjnego, którego dane wejściowe to formuła 3CNF , a których wynikiem jest liczba taka, że mieści się w zakresie współczynnik multiplikatywny od , gdzie jest absolutną stałą dodatnią.M ( C ) C C M ′ M ( C ) 1 + c M ′ c > $C$$M(C)$$C$$C$$M'$$M(C)$$1+c$$M'$$c>0$

Uważam, że NP jest również trudne do obliczenia dla dowolnego stałego modułu p . Zastanawiam się, czy prawdą jest następujące wspólne uogólnienie tych dwóch faktów: Nie ma algorytmu czasu policyjnego, którego dane wejściowe to formuła C 3CNF z klauzulami N i ciąg bitów \ log_2 NB , a wynik to M (C) . Tutaj B jest absolutną stałą. Krótko mówiąc, nie ma algorytmu obliczającego B bitów informacji M (C) .$M(C) \bmod p$$p$$C$$N$$\log_2 N-B$$M(C)$$B$$B$$M(C)$

Przepraszam, jeśli pytanie ma dobrze znaną odpowiedź, ponieważ nie jestem teoretykiem złożoności na podstawie tła.

Oto argument, że gdybyś mógł rozwiązać Max 3SAT na instancji klauzuli m przy stałej liczbie bitów porady, wówczas hierarchia wielomianowa upadłaby.

Napraw problem NP-zupełny L. Z twierdzenia Cooka wiemy, że transformacja f () danych wejściowych x dla L na formuły 3SAT f (x), tak że

1) jeśli to$x\in L$$M(f(x)) = m$

2) jeśli to$x\in L$$M(f(x)) = m-1$

gdzie jest liczbą zdań w .$m$$f(x)$

Mamy także twierdzenie Kadina, że ​​mówi się, że jeśli podano danych wejściowych problemu NP-zupełnego, masz algorytm wielomianowy, który sprawia, że zapytania do wyroczni NP i określa prawidłowa odpowiedź na problemów NP , wówczas hierarchia wielomianowa się zawala.$k$$x_1,\ldots,x_k$$\leq k-1$$k$$x_i \in ? L$

Załóżmy, że mamy algorytm, który rozwiązuje Max SAT na wejściach klauzuli m, biorąc pod uwagę k bitów porady. Wykorzystamy wynik Hastada do skonstruowania algorytmu, tak jak w założeniu twierdzenia Kadina.

Początek z wejść problemowemu . Zastosuj twierdzenie Cooka do każdego z nich. Po pewnej normalizacji (co można zrobić, przypisując wagi do klauzul lub duplikując je, jeśli nie chcemy używać wag), konstruujemy formuły gdzie dla pewnego :$K=2^k+1$$x_1,\ldots,x_K$$L$$K$$F_1,\ldots,F_K$$m$

1) jeśli a przeciwnym razie$M(F_1)= m-1$$x_1 \in L$$M(F_1) = m-2$

2) jeśli a przeciwnym razie$M(F_2) = m\cdot (m-1)$$x_2 \in L$$M(F_2) = m\cdot (m-2)$

...

k) jeśli i przeciwnym razie$M(F_K) = m^{K-1} \cdot (m-1)$$x_K\in L$$M(F_K) = m^{K-1} \cdot (m-2)$

Teraz weź unię formuł, które zostały zbudowane w ciągu rozłącznych zbiorów zmiennych i nazwać . Mamy więc i możemy „odczytać” odpowiedź na problemów patrząc w wyjś- reprezentacji . Jeśli możemy obliczyć podane bitów radę, to znaczy, że możemy znaleźć wartości takie, że jeden z nich jest . Możemy następnie zapytać nieadaptacyjnie wyrocznię NP, czy dla każdej z wartości kandydujących$F$$M(F) = M(F_1) + \cdots + M(F_k)$$K$$x_i \in? L$$m$$M(F)$$M(F)$$k$$2^k$$M(F)$$M(F) \geq n_i$$n_1,\ldots,n_{2^k}$wygenerowaliśmy. Tak więc byliśmy w stanie rozwiązać problemów z NP-zupełnym wykonaniem nieadaptacyjnych zapytań do wyroczni NP, co oznacza, że ​​hierarchia wielomianowa się zawali.$2^k+1$$2^k$

Używając twierdzenia Hastada zamiast twierdzenia Cooka, możliwe jest przesunięcie wielkości do zamiast , więc możliwe jest przesunięcie do , a liczba bitów porady do . Zrozumienie, co się dzieje, gdy otrzymasz bity porady, wydaje się naprawdę trudne.$F$$O(1)^k \cdot m$$m^k$$k$$\log m$$\log\log m$$\log m - O(1)$

Zredagowano, aby dodać: Krentel ( The Complexity of Optimization Problems . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) udowodnił, że obliczenie wartości optymalnej dla problemu maksymalnego kliku jest kompletne dla , klasa funkcji obliczalnych w czasie wielomianowym z zapytaniami do wyroczni NP. Kompletność jest pod „redukcjami o jedno zapytanie”, w których funkcja f jest redukowalna do funkcji g, jeśli można napisać dla obliczalnego czasu wielomianowego i . Przypuszczalnie to samo jest prawdą dla Maxa Clique. Teraz, jeśli Max Clique miał algorytm wielomianowy, który tworzy listę$FP^{NP[O(log n)]}$$O(log n)$$f(x) = r_1(g(r_2(x))$$r_1$$r_2$$m^{o(1)}$możliwych wartości, byłoby to w , ponieważ można użyć wyszukiwania binarnego, aby znaleźć optymalną liczbę zapytań, które są dziennikiem wielkości listy.$FP^{NP[o(logn)]}$

Teraz, jeśli mamy pewno mielibyśmy , który jest szczególnym przypadkiem problemów decyzyjnych i jest znany z wyników Wagnera (poprawiającego wynik Kadina, który dotyczy stałej liczby zapytań), w celu zwinięcia hierarchii wielomianowej. Myślę jednak, że może być wiadome, że faktycznie oznacza P = NP. Ale w każdym razie wyniki Krentela i Kadina-Wagnera powinny wystarczyć, aby dać kolejny dowód na wynik Andy'ego Druckera. Teraz zastanawiam się, czy faktycznie jest to ten sam dowód, to znaczy, czy wynik Fortnow-Van Melkebeek działa, jawnie lub pośrednio, za pomocą argumentu „symulującego zapytania NP z mniejszą liczbą zapytań NP”.$FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$$P^{NP[O(log n)]} = P^{NP[o(log n)]}$$FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$

Dobry artykuł ankietowy wyjaśniający, co dzieje się z problemami dotyczącymi optymalizacji i ograniczonymi klasami zapytań:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Chciałbym podać jeden powód, dla którego udowodnienie twardości NP tego problemu jest trudne.

W komentarzu do pytania Luca Trevisan podał dobry sposób na odtworzenie problemu: Czy następujący problem można rozwiązać w czasie wielomianowym dla każdego stałego k ? Biorąc pod uwagę wzór CNF C z klauzulami m , wyprowadzaj co najwyżej liczby całkowite m / k , aby jedna z nich była równa M ( C ). Tutaj k jest związany z B przez k = 2 ^pensjonatów .

Żądajmy jednak więcej. Rozważamy następujący problem: biorąc pod uwagę wzór CNF C , wypisz dwie liczby całkowite, aby jedna z nich była równa M ( C ). Problem ten oznaczamy jako Π. Problem Π jest co najmniej tak trudny, jak problem pierwotny, więc jeśli pierwotny problem jest trudny NP, Π musi być również trudny NP.

Zauważ, że Π jest problemem związanym z relacjami. Jednym z najprostszych rodzajów redukcji, które można zastosować w celu zredukowania problemu L do problemu relacji Π, jest redukcja Levina w czasie wielomianowym, która jest szczególnym przypadkiem redukcji Turinga w czasie wielomianowym, gdzie redukcja wywołuje wyrocznię tylko dla Π pewnego razu.

Twierdzimy, że P ^{Π [1]} = P. To oczywiście implikuje, że NP⊈P ^{Π [1],} chyba że P = NP, to znaczy, że Π nie jest NP-twardy przy wielomianowej redukcji Levina, chyba że P = NP.

Dowód . Niech L ∈P ^{Π [1]} , czyli innymi słowy, istnieje redukcja Levina z L do Π. Oznacza to, że istnieje para ( f , g ) obliczalnej funkcji wielomianowej f : {0,1} ^* → {0,1} ^*, która odwzorowuje każdą instancję x problemu L na pewną formułę CNF f ( x ) oraz predykat obliczalny w czasie wielomianowym g : {0,1} ^* × ℕ × ℕ → {0,1} taki, że g ( x , i , j ) = L( x ) jeśli albo i lub j jest równe M ( f ( x )). (Tutaj L ( x ) = 1, jeśli x jest instancją typu L dla L, a L ( x ) = 0, jeśli x jest instancją typu nie.)

Z tego konstruujemy algorytm czasu wielomianowego dla L w następujący sposób. Niech x będzie wejściem.

1. Niech C = f ( x ) i pozwolić m jest liczbą z klauzul C .
2. Znajdź jeden i ∈ {0,…, m } taki, że wartość g ( x , i , j ) jest stała niezależna od j ∈ {0,…, m }.
3. Wyprowadź tę stałą g ( x , i , 0).

W kroku 2 takie i zawsze istnieje, ponieważ i = M ( f ( x )) spełnia warunek. Co więcej, ten algorytm nie może dać złej odpowiedzi, ponieważ g ( x , i , M ( f ( x ))) musi być poprawną odpowiedzią. Dlatego ten algorytm rozwiązuje L poprawnie. QED .

Jeśli się nie mylę, ten sam pomysł można wykorzystać do udowodnienia, że ​​P ^{Π [ k ( n )]} ⊆DTIME [ n ^{O ( k ( n ))} ]. Oznacza to, że NP⊈P ^{Π [ k ]} dla dowolnej stałej k, chyba że P = NP i że NP⊈P ^{Π [polilog],} chyba że NP⊆DTIME [2 ^polilog ]. Jednak sama ta idea nie wyklucza możliwości, że Π jest trudny do uzyskania w warunkach wielomianowej redukowalności Turinga.

Wierzę, że możemy pokazać:

Roszczenie. Jest wartość taka, że ​​następujące są prawdziwe. Załóżmy, że istnieje deterministyczny algorytm wieloczasowy , który, biorąc pod uwagę klauzulę instancję 3-SAT , wyświetla listę o wartościach co najwyżej , takich jak ; wtedy hierarchia wielomianowa się zapada.$0 < c < 1$$m$$\phi$$S$$m^c$$M(\phi) \in S$

Dowód wykorzystuje wyniki Fortnow i Santhanam dotyczące niemożności kompresji instancji z ich papieru http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

W szczególności, patrząc na dowód Thm 3.1, wydaje mi się, że można wyodrębnić następujące elementy (wkrótce to sprawdzę ponownie):

„Twierdzenie” [FS]. Istnieją liczby całkowite takie, że poniższe są prawdziwe. Załóżmy, że w deterministycznym czasie wieloczasowym można przekształcić OR formuł boolowskich (każda o długości , i na rozłącznych zestawach zmiennych) w OR o formułach (ponownie zmienna rozłączna i długości ), zachowując zadowalającą / niezadowalającą RNO. Następnie i hierarchia wielomianowa się załamuje.$0 < d' < d$$n^d$$\leq n$$n^{d'}$$\leq n$$\mathsf{NP} \subseteq \mathsf{coNP/poly}$

Dowodem naszego twierdzenia będzie redukcja zadania kompresji OR wspomnianego w powyższym twierdzeniu [FS] do problemu obliczania listy . Załóżmy, że to lista formuł, których OR chcemy skompresować.$M(\phi)$$\psi_1, \ldots, \psi_{n^d}$

Pierwszy krok: zdefiniuj obwód wielomianowy na ciągach wejściowych . Tutaj ciąg koduje przypisanie do , a koduje liczbę od do .$\Gamma$$(v, y_1, \ldots, y_{n^d})$$y_i$$\psi_i$$v \in \{0, 1\}^{d \log n + 1}$$0$$n^d$

Mamy akceptuje iff albo , albo .$\Gamma$$v = 0$$\psi_v(y_v) = 1$

Teraz niech oznacza maksymalną wartość , tak że ograniczony obwód jest wystarczający. (Ta ilość wynosi zawsze co najmniej 0).$M^*(\Gamma)$$v$$\Gamma(v, \cdot, \ldots, \cdot)$

Załóżmy, że możemy skutecznie stworzyć listę możliwych wartości dla . Zatem twierdzenie jest takie, że na naszej liście , możemy wyrzucić wszystkie dla których ; powstała lista zawiera satysfakcjonującą formułę, taką jak pierwotna. Mam nadzieję, że dzięki inspekcji jest to jasne.$S$$M^*(\Gamma)$$\psi_1, \ldots, \psi_{n^d}$$\psi_i$$i \notin S$

Wniosek: nie można niezawodnie wytwarzać listy o możliwych wartości dla , o ile poli załamuje struktury.$S$$\leq n^{d'}$$M^*(\Gamma)$

Drugi krok: redukujemy problem obliczania listy do problemu obliczania listy dla instancji 3-SAT .$M^*(\Gamma)$$M(\phi)$$\phi$

Aby to zrobić, najpierw uruchamiamy redukcję Cooka na aby uzyskać instancję 3-SAT o rozmiarze . ma taki sam zestaw zmiennych jak , a także niektóre zmienne pomocnicze. Najważniejsze dla naszych celów jest to, że jest zadowalający iff jest zadowalający.$\Gamma$$\phi_1$$m = poly(n^d)$$\phi_1$$\Gamma$$\phi_1(v, \cdot)$$\Gamma(v, \cdot)$

Nazywamy „silnymi ograniczeniami”. Każdemu z tych ograniczeń wagę (poprzez dodanie duplikatów ograniczeń).$\phi_1$$2m$

Następnie dodajemy zestaw `` słabych ograniczeń '' które dodają preferencję, aby indeks (zdefiniowany w kroku 1) był jak najwyższy. Dla każdego bitu z istnieje jedno ograniczenie , a mianowicie . Pozwalamy, aby -ty najbardziej znaczący bit miał ograniczenie masy . Ponieważ ma długość , wagi te mogą być zintegrowane (wystarczy, że padniemy, aby było potęgą 2).$\phi_2$$v$$v_t$$v$$[v_t = 1]$$t$$v$$m/2^{t-1}$$v$$d \log n + 1$$m$

Wreszcie, niech będzie wynikiem naszej redukcji.$\phi = \phi_1 \wedge \phi_2$

Aby przeanalizować , niech będzie zbiorem zmiennych , przy czym jak poprzednio. Po pierwsze zauważmy, że biorąc pod uwagę dowolne przypisanie do , wartość można wywnioskować z ilości (całkowita waga ograniczeń spełnionych przez ). Wynika to z hierarchicznego projektowania wag ograniczających (podobnie jak technika z odpowiedzi Lucy). Podobnie, maksymalna osiągalna wartość jest osiągana przez ustawienie które spełnia wszystkie silne ograniczenia, i gdzie (z zastrzeżeniem)$\phi$$(v,z)$$\phi$$v$$(v, z)$$v$$N(v, z) =$$\phi$$v, z$
$M(\phi)$$(v, z)$$v$jest tak duży, jak to możliwe. To jest największym indeksem, dla którego jest zadowalający, a mianowicie . (Uwaga: zawsze można ustawić all-0, aby spełnić wszystkie silne ograniczenia, ponieważ w takim przypadku jest zadowalające.)$v$$\Gamma(v, \cdot)$$M^*(\Gamma)$$v =$$\Gamma(v, \cdot)$

Wynika z tego, że jeśli otrzymamy listę możliwych wartości , możemy uzyskać listęmożliwe wartości . Zatem nie możemy mieć chyba że hierarchia poli upadnie. To daje Roszczenie, ponieważ .$S$$M(\phi)$$|S|$$M^*(\Gamma)$$|S| \leq n^{d'}$$n^{d'} = m^{\Omega(1)}$