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 1 ∨ x 2 ∨ x 4 ) ∧ (¬x 1 ∨¬x 3 ∨ x 4 ) ∧ ( x 1 ∨ x 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
źródło
Odpowiedzi:
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:Φ
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 Φ 2Nn2 1153Nn2 n=Nkm=Nk+1C=11113Nn2 n=Nk m=Nk+1 k=ϵ-1-1C∝m2-ϵC=113N2k+1=113m2−1k+1 k=ϵ−1−1 C∝m2−ϵ
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 a ≠ y i b a , b n - 1 ( 1 - s ) N a , b y : a y : b y : ( a + b ) 1 - sϕ (1−s)N yia≠yib a,b n−1 (1−s)N a,b y:a y:b y:(a+b) 1-s1−s5N ab≈1-s1−s5N(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 .≈1−s5Nn2=3(1−s)11C (1−s)Nn2=(1−s)m2k+1k+1=(1−s)C s′=4+s5
Stałe prawdopodobnie należy dwukrotnie sprawdzić.
źródło