Obliczanie wszelkich informacji o Max-3SAT

26

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 > 0CM(C)CCMM(C)1+cMc>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)modppCNlog2NBM(C)BBM(C)

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

Boris Bukh
źródło
1
Zwykle „rada” może zależeć tylko od długości danych wejściowych. Uważam, że Twoim celem jest, aby „rada” tutaj mogła zależeć od samego wkładu. Nie znam standardowej terminologii dla tego pojęcia.
Tsuyoshi Ito
9
To bardzo interesujące pytanie. Aby potwierdzić, że M(C)modp jest rzeczywiście trudny do obliczenia, można zauważyć, że dowód twierdzenia Cooka daje m zmienną formułę F która jest albo zadowalająca, albo taka, że M(F)=m1 .
Luca Trevisan
16
Pytanie można powtórzyć w następujący sposób: czy może istnieć wielomianowy algorytm czasowy, który przy wzorze 3CNF F ze zmiennymi m , wyświetla listę liczb m/2B tak że jedną z tych liczb jest M(F) ?
Luca Trevisan
2
tak, m powinna być liczbą klauzul w powyższym komentarzu.
Luca Trevisan
9
jest to równoważne, ponieważ jeśli masz algorytm opisany w poście, możesz uruchomić algorytm na każdym z 2log2mB=m/2B możliwych ciągów porad 2 ^ {\ log_2 m - B} = m / 2 ^ B , otrzymaj tyle (lub mniej, jeśli są kolizje) odpowiedzi, a jedna z nich jest poprawna. Jeśli masz algorytm jak w moim komentarzu powyżej, log2mB bity porady B są wystarczające, aby określić, że poprawna odpowiedź jest i największą z wyników algorytmu, dla niektórych i .
Luca Trevisan

Odpowiedzi:

14

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 toxLM(f(x))=m

2) jeśli toxLM(f(x))=m1

gdzie jest liczbą zdań w .mf(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.kx1,,xkk1kxi?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=2k+1x1,,xKLKF1,,FKm

1) jeśli a przeciwnym razieM(F1)=m1x1LM(F1)=m2

2) jeśli a przeciwnym razieM(F2)=m(m1)x2LM(F2)=m(m2)

...

k) jeśli i przeciwnym razieM(FK)=mK1(m1)xKLM(FK)=mK1(m2)

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ącychFM(F)=M(F1)++M(Fk)Kxi?LmM(F)M(F)k2kM(F)M(F)nin1,,n2kwygenerowaliś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.2k+12k

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.FO(1)kmmkklogmloglogmlogmO(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ęFPNP[O(logn)]O(logn)f(x)=r1(g(r2(x))r1r2mo(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.FPNP[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”.FPNP[O(logn)]=FPNP[o(logn)]PNP[O(logn)]=PNP[o(logn)]FPNP[O(logn)]=FPNP[o(logn)]

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

Luca Trevisan
źródło
8

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.

Tsuyoshi Ito
źródło
1
Czy możesz podać link do odpowiedzi Dany?
Mohammad Al-Turkistany
@turkistany: Usunęła swoją odpowiedź po opublikowaniu pierwszej wersji tej odpowiedzi. Właśnie usunąłem odniesienie do tego z tej odpowiedzi.
Tsuyoshi Ito
8

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<1mϕSmcM(ϕ)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<dndnndnNPcoNP/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(ϕ)ψ1,,ψnd

Pierwszy krok: zdefiniuj obwód wielomianowy na ciągach wejściowych . Tutaj ciąg koduje przypisanie do , a koduje liczbę od do .Γ(v,y1,,ynd)yiψiv{0,1}dlogn+10nd

Mamy akceptuje iff albo , albo .Γv=0ψv(yv)=1

Teraz niech oznacza maksymalną wartość , tak że ograniczony obwód jest wystarczający. (Ta ilość wynosi zawsze co najmniej 0).M(Γ)vΓ(v,,,)

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.SM(Γ)ψ1,,ψndψiiS

Wniosek: nie można niezawodnie wytwarzać listy o możliwych wartości dla , o ile poli załamuje struktury.SndM(Γ)

Drugi krok: redukujemy problem obliczania listy do problemu obliczania listy dla instancji 3-SAT .M(Γ)M(ϕ)ϕ

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.Γϕ1m=poly(nd)ϕ1Γϕ1(v,)Γ(v,)

Nazywamy „silnymi ograniczeniami”. Każdemu z tych ograniczeń wagę (poprzez dodanie duplikatów ograniczeń).ϕ12m

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).ϕ2vvtv[vt=1]tvm/2t1vdlogn+1m

Wreszcie, niech będzie wynikiem naszej redukcji.ϕ=ϕ1ϕ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)ϕ(v,z)ϕv(v,z)vN(v,z)=ϕv,z
M(ϕ)(v,z)vjest 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Γ(v,)M(Γ)v=Γ(v,)

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ż .SM(ϕ)|S|M(Γ)|S|ndnd=mΩ(1)

Andy Drucker
źródło