Czy Gap-3SAT NP-zupełny jest nawet dla formuł 3CNF, w których żadna para zmiennych nie pojawia się w znacznie większej liczbie klauzul niż średnia?

32

W tym pytaniu formuła 3CNF oznacza formułę CNF, w której każda klauzula obejmuje dokładnie trzy różne zmienne. Dla stałych 0 < s <1, Gap-3SAT s stanowi następujący problem:

GAP 3SAT s
wystąpienia : a 3CNF wzór φ.
Tak, obietnica : φ jest satysfakcjonująca.
No-obietnica : Brak przypisania prawda spełniać więcej niż ów ułamek klauzul cp.

Jednym z równoważnych sposobów sformułowania znanego twierdzenia PCP [AS98, ALMSS98] jest istnienie stałej 0 < s <1 takiej, że Gap-3SAT s jest NP-zupełny.

Mówimy, że formuła 3CNF jest powiązana parami B, jeśli każda para różnych zmiennych występuje w co najwyżej klauzulach B. Na przykład formuła 3CNF ( x 1x 2x 4 ) ∧ (¬x 1 ∨¬x 3x 4 ) ∧ ( x 1x 3 ∨¬x 5 ) jest powiązana parami 2, ale nie parą 1 -związane, ponieważ np. para ( x 1 , x 4 ) występuje w więcej niż jednej klauzuli.

Pytanie . Czy istnieje stałe B ∈ℕ, > 0 i 0 < y <1, że szczelinę 3SAT y jest NP-zupełny nawet wzoru 3CNF która parami B -bounded i składa się z co najmniej an dwóch punktach, w których n jest liczba zmiennych?

Ograniczenie parami wyraźnie sugeruje, że istnieją tylko klauzule O ( n 2 ). Wraz z kwadratową dolną granicą liczby klauzul, z grubsza mówi, że żadna para odrębnych zmiennych nie pojawia się w znacznie większej liczbie klauzul niż średnia.

W przypadku Gap-3SAT wiadomo, że rzadki przypadek jest trudny : istnieje stała 0 < s <1, tak że Gap-3SAT s jest NP-zupełny nawet dla wzoru 3CNF, w którym każda zmienna występuje dokładnie pięć razy [Fei98]. Z drugiej strony, gęsty przypadku łatwo Max-3SAT przyznaje się PTA formuły 3CNF z Ohm ( n- 3 ) różnych punktach [AKK99], a zatem szczelinę 3SAT a w tym przypadku w P każdej stałej 0 < s <1. Pytanie dotyczy środka tych dwóch przypadków.

Powyższe pytanie powstało pierwotnie w badaniu kwantowej złożoności obliczeniowej, a dokładniej w dwóch okrągłych, interaktywnych systemach dowodowych z podwójnym dowodzeniem i systemami splątanych ( MIP * (2,1) ). Myślę jednak, że pytanie może samo w sobie być interesujące.

Referencje

[AKK99] Sanjeev Arora, David Karger i Marek Karpinski. Schematy aproksymacji czasu wielomianowego dla gęstej instancji problemów trudnych dla NP. Journal of Computer Sciences i systemowe , 58 (1): 193-210, luty 1999. http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan i Mario Szegedy. Weryfikacja dowodu i stopień trudności problemów z aproksymacją. Journal of the ACM , 45 (3): 501-555, maj 1998 http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora i Shmuel Safra. Probabilistyczne sprawdzanie dowodów: nowa charakterystyka NP. Journal of the ACM , 45 (1): 70–122, styczeń 1998. http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige. Próg ln n dla przybliżenia zestawu osłon. Journal of the ACM , 45 (4): 634–652, lipiec 1998. http://doi.acm.org/10.1145/285055.285059

Tsuyoshi Ito
źródło
@Tsuyoshi: czy mam rację, zakładając, że nic nie wiadomo o innych przypadkach pośrednich, między i ? m = Ω ( n 3 )m=O(n)m=Ω(n3)
András Salamon,
1
@ András: Nie znam żadnych wcześniejszych wyników dotyczących przypadków pośrednich, ale mam, jak sądzę, dowód na kompletność NP następujących przypadków. (1) Klauzule sparowane, , ale bez przerwy. (2) Z przerwą, zdania dla dowolnej stałej d <3, ale niekoniecznie ograniczonej parami. (3) Z przerwą, parami, dla dowolnej stałej d <2. Dowód (1) jest prostą redukcją z [Fei98]. Dowód (2) wykorzystuje część wyniku Ailon i Alon 2007 . Dowód (3) używa ekspanderów. Ω ( n d ) Ω ( n d )Ω(n2)Ω(nd)Ω(nd)
Tsuyoshi Ito
1
@Tsuyoshi: Nie mogę się doczekać, aby przeczytać artykuł.
András Salamon
4
Nie ma odpowiedzi, ale chciałbym sprawdzić, czy metody stwierdzam, że losowy 3CNF klauzul m wynosi unsatisfiable może odnieść sukces tutaj w pokazywaniu tego problemu jest proste, przynajmniej jeśli wymagana solidność być blisko 7/8. Prace te zakończą się powodzeniem, gdy pojawi się więcej niż klauzul i zostały rozszerzone na modele pół losowe (patrz Feige FOCS 07 na temat obalenia wygładzonego 3CNF). Wydaje się jednak, że Tsuyoshi pokazał, że nawet przypadek tutaj jest nadal NP-trudny, więc może to pokazuje, że te prace nie są istotne. n 1,5 n 1,9sn1.5n1.9
Boaz Barak,
7
Boaz, zawsze możesz „zagęścić” instancję 3SAT, zastępując każdą zmienną kopiami, a następnie zastępując każdą klauzulę klauzulami , zastępując każdą zmienną w oryginalnej klauzuli kopiami na wszystkie możliwe sposoby. Daje to instancję, w której ta sama część klauzul jak poprzednio jest zadowalająca, ale przechodzisz od n zmiennych i klauzul m do zmiennych nM i klauzul , więc bez dalszego ograniczenia liczby wystąpień możesz zachować poprawność nawet w formułach z zmiennymi i klauzulami . K 3 m M 3 7 / 8 + ε N N 2.999MM3mM37/8+ϵNN2.999
Luca Trevisan

Odpowiedzi:

6

Nie pełna odpowiedź, ale mam nadzieję, że blisko. Jest to bardzo zbliżone do powyższych komentarzy Lucy. Uważam, że odpowiedź jest taka, że przynajmniej tam zrobić stałe istnieć B ∈ℕ, a > 0 i 0 < s <1 takie, że Gap-3SAT s jest NP-zupełny nawet formuły 3CNF który jest parami B -bounded i składa się z co najmniej klauzule , dla każdej stałej . ϵan2ϵϵ

Dowód jest następujący. Rozważ instancję GAP- na zmiennych, w których każda zmienna pojawia się najwyżej 5 razy. To jest NP-zupełne, jak mówisz w pytaniu. ϕ NsϕN

Teraz tworzymy nową instancję w następujący sposób:Φ

  1. Dla każdej zmiennej w , ma zmiennych . ϕ Φ n y i jxiϕΦnyij
  2. Dla każdego zestawu indeksów , i z , ma parę klauzul i . Odniosę się do nich jako do klauzul porównawczych, ponieważ zapewniają one, że jeśli są spełnione.a b a b Φ y i ay i by i b y i by i ay i a y i a = y i biababΦyiayibyibyibyiayiayia=yib
  3. Dla każdej klauzuli działającej na zmienne , i , dla każdego i , zawiera równoważną klauzulę, w której jest zastąpione przez , jest zastąpione przez a jest zastąpione autor: (tutaj dodaje się modulo ). Będę się nazywać tymi klauzulami dziedziczonymi.x i x j x k a b Φ x i y i a x j y j b x k y k ( a + b ) nϕxixjxkabΦxiyiaxjyjbxkyk(a+b)n

Całkowita liczba zmiennych wynosi wtedy . Uwaga ma klauzule porównawcze i odziedziczone klauzule, w sumie klauzule . Biorąc mamy i całkowitą liczbę klauzul . Bierzemy , więc .Φ 2 N n 2 5m=nNΦ2Nn21153Nn2n=Nkm=Nk+1C=11113Nn2n=Nkm=Nk+1 k=ϵ-1-1Cm2-ϵC=113N2k+1=113m21k+1k=ϵ11Cm2ϵ

Następnie jest parami ograniczone do 8 (maksymalnie 2 z klauzul porównawczych i 6 z klauzul odziedziczonych).Φ

Wreszcie, jeśli jest niezadowalająca, to co najmniej klauzule są niespełnione. Teraz, jeśli dla dowolnego to co najmniej klauzule są niespełnione. Zauważ, że aby spełnić niezadowolonych klauzul w zestawie dziedziczonych klauzul dla ustalonych następnie przypisanie zmiennych , i musi różnić się co najmniej pozycji, pozostawiając co najmniej klauzule niezadowalające. Musi to dotyczyć każdego wyboru i( 1 - s ) N y i ay i b a , b n - 1 ( 1 - s ) N a , b y : a y : b y : ( a + b ) 1 - sϕ(1s)Nyiayiba,bn1(1s)Na,by:ay:by:(a+b)1-s1s5Nab1-s1s5N(n1)ab, więc co najmniej Klauzule porównawcze muszą pozostać niezadowolone w całości, aby spełnić wystarczającą liczbę klauzul odziedziczonych. Jeśli jednak spojrzysz na drugą skrajność, w której spełnione są wszystkie klauzule porównania, to Klauzule są niezadowalające. Stąd pozostaje przerwa (choć zmniejszona) z .1s5Nn2=3(1s)11C(1s)Nn2=(1s)m2k+1k+1=(1s)Cs=4+s5

Stałe prawdopodobnie należy dwukrotnie sprawdzić.

Joe Fitzsimons
źródło
Dziękuję Joe. Przepraszam, jeśli nie było to jasne, ale w tym pytaniu wymagam, aby wszystkie trzy zmienne w każdej klauzuli były wszystkie odrębne, a zatem nie można używać klauzul porównawczych, gdy są one zapisane. Mam dowód na ten sam fakt (powiązane parami, klauzule Ω (n ^ (2 − ε)), z przerwą), który wykorzystuje wykresy ekspanderów, ale jeśli można to udowodnić bez użycia ekspanderów, jestem bardzo zainteresowany.
Tsuyoshi Ito,
@Tsuyoshi: Ach, rozumiem. Właściwie początkowo udowodniłem to sobie za pomocą odrębnych zmiennych, więc jest bardzo łatwy tweek, aby uzyskać pożądaną formę. Po prostu przypisujesz klauzule porównawcze w nieco inny sposób. Zamiast dwóch klauzul, które ci dałem, potrzebujesz 4: , , i . Oczywiste jest, że redukują one do tych samych 2 zmiennych zmiennych, co poprzednio. Oczywiście to poprawia stałe, ale nie robi żadnej różnicy. yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)
Joe Fitzsimons,
Być może istnieje sposób na obejście czynnika , przyjmując , chociaż najbardziej naiwna implementacja tego daje instancje, które rosną bardzo nieznacznie szybciej niż wielomianowo. k = k ( n )ϵk=k(n)
Joe Fitzsimons,
Dokładniej sprawdzę szczegóły później, ale wydaje się, że pomysł użycia a, b i (a + b) działa. To powinno mnie uwolnić od jawnego traktowania ekspanderów. Dzięki!
Tsuyoshi Ito,
Nie ma problemu. Cieszę się, że mogłem pomóc.
Joe Fitzsimons,