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?

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 ₁ ∨ x ₂ ∨ x ₄ ) ∧ (￢x ₁ ∨￢x ₃ ∨ x ₄ ) ∧ ( x ₁ ∨ x ₃ ∨￢x ₅ ) jest powiązana parami 2, ale nie parą 1 -związane, ponieważ np. para ( x ₁ , x ₄ ) 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 ² ). 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- ³ ) 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

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 .$an^{2-\epsilon}$$\epsilon$

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. ϕ $_s$$\phi$$N$

Teraz tworzymy nową instancję w następujący sposób:$\Phi$

1. Dla każdej zmiennej w , ma zmiennych . ϕ Φ n y i $x_i$$\phi$$\Phi$$n$$y_{ij}$
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 a ∨ ￢y i b ∨ ￢y i b y i b ∨ ￢y i a ∨ ￢y i a y i a = y i $i$$a$$b$$a\neq b$$\Phi$$y_{ia}∨￢y_{ib}∨￢y_{ib}$$y_{ib}∨￢y_{ia}∨￢y_{ia}$$y_{ia} = y_{ib}$
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 )$\phi$$x_i$$x_j$$x_k$$a$$b$$\Phi$$x_i$$y_{ia}$$x_j$$y_{jb}$$x_k$$y_{k(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 $m = nN$$\Phi$$2Nn^2$$\frac{5}{3}Nn^2$n=Nkm=Nk+1C=$\frac{11}{3}Nn^2$$n = N^k$$m = N^{k+1}$ k=ϵ-1-1C∝m2-$C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$$k = \epsilon^{-1} - 1$$C \propto m^{2-\epsilon}$

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

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 a ≠ y i b a , b n - 1 ( 1 - s ) N a , b y : a y : b y : ( a + b ) 1 - $\phi$$(1-s)N$$y_{ia} \neq y_{ib}$$a,b$$n-1$$(1-s)N$$a,b$$y_{:a}$$y_{:b}$$y_{:(a+b)}$1-$\frac{1-s}{5}N$ab≈1-$\frac{1-s}{5}N(n-1)$$a$$b$, 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 .$\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$$(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$$s' = \frac{4+s}{5}$

Stałe prawdopodobnie należy dwukrotnie sprawdzić.