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 > 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) .
Przepraszam, jeśli pytanie ma dobrze znaną odpowiedź, ponieważ nie jestem teoretykiem złożoności na podstawie tła.
źródło
Odpowiedzi:
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 tox∈L M(f(x))=m
2) jeśli tox∈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 x1,…,xk ≤k−1 k xi∈?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+1 x1,…,xK L K F1,…,FK m
1) jeśli a przeciwnym razieM(F1)=m−1 x1∈L M(F1)=m−2
2) jeśli a przeciwnym razieM(F2)=m⋅(m−1) x2∈L M(F2)=m⋅(m−2)
...
k) jeśli i przeciwnym razieM(FK)=mK−1⋅(m−1) xK∈L M(FK)=mK−1⋅(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ącychF M(F)=M(F1)+⋯+M(Fk) K xi∈?L m M(F) M(F) k 2k M(F) M(F)≥ni n1,…,n2k 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.2k+1 2k
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⋅m mk k logm loglogm logm−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ęFPNP[O(logn)] O(logn) f(x)=r1(g(r2(x)) r1 r2 mo(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
źródło
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.
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.
źródło
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 ϕ S mc M(ϕ)∈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 nd ≤n nd′ ≤n NP⊆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(ϕ) ψ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 ψi v∈{0,1}dlogn+1 0 nd
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.S M∗(Γ) ψ1,…,ψnd ψi i∉S
Wniosek: nie można niezawodnie wytwarzać listy o możliwych wartości dla , o ile poli załamuje struktury.S ≤nd′ M∗(Γ)
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.Γ ϕ1 m=poly(nd) ϕ1 Γ ϕ1(v,⋅) Γ(v,⋅)
Nazywamy „silnymi ograniczeniami”. Każdemu z tych ograniczeń wagę (poprzez dodanie duplikatów ograniczeń).ϕ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).ϕ2 v vt v [vt=1] t v m/2t−1 v dlogn+1 m
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) v N(v,z)= ϕ v,z
M(ϕ) (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 Γ(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ż .S M(ϕ) |S| M∗(Γ) |S|≤nd′ nd′=mΩ(1)
źródło