¿Está Gap-3SAT NP completo incluso para fórmulas 3CNF donde no aparece ningún par de variables en significativamente más cláusulas que el promedio?

32

En esta pregunta, una fórmula 3CNF significa una fórmula CNF donde cada cláusula involucra exactamente tres variables distintas . Para una constante 0 < s <1, Gap-3SAT s es el siguiente problema prometedor:

Gap-3SAT s
Instancia : fórmula φ A 3CNF.
Sí, prometo : φ es satisfactoria.
Sin promesa : ninguna asignación de verdad satisface más de una fracción de las cláusulas de φ.

Una de las formas equivalentes de enunciar el famoso teorema de PCP [AS98, ALMSS98] es que existe una constante 0 < s <1 tal que Gap-3SAT s es NP-completo.

Decimos que una fórmula 3CNF está limitada por pares B si cada par de variables distintas aparece en la mayoría de las cláusulas B. Por ejemplo, una fórmula 3CNF ( x 1x 2x 4 ) ∧ (¬x 1 ∨¬x 3x 4 ) ∧ ( x 1x 3 ∨¬x 5 ) está emparejada en 2 pero no está emparejada en pares 1 limitado porque, por ejemplo, el par ( x 1 , x 4 ) aparece en más de una cláusula.

Cuestión . No existen constantes B ∈ℕ, una > 0, y 0 < s <1 tal que Gap-3SAT s es NP-completo incluso para una fórmula 3CNF que es pairwise B -bounded y consta de al menos un 2 cláusulas, donde n es el numero de variables?

La delimitación por pares implica claramente que solo hay cláusulas O ( n 2 ). Junto con el límite inferior cuadrático en el número de cláusulas, más o menos dice que ningún par de variables distintas aparece en significativamente más cláusulas que el promedio.

Para Gap-3SAT, se sabe que el caso disperso es difícil : existe una constante 0 < s <1 tal que Gap-3SAT s es NP-completo incluso para una fórmula 3CNF donde cada variable ocurre exactamente cinco veces [Fei98]. Por otro lado, el caso denso es fácil : Max-3SAT admite un PTAS para una fórmula 3CNF con cláusulas distintas Ω ( n 3 ) [AKK99], y por lo tanto Gap-3SAT s en este caso está en P para cada constante 0 < s <1. La pregunta se refiere a la mitad de estos dos casos.

La pregunta anterior surgió originalmente en un estudio de la complejidad computacional cuántica, más específicamente sistemas de prueba interactivos de una ronda de dos probadores con probadores enredados (sistemas MIP * (2,1) ). Pero creo que la pregunta puede ser interesante por derecho propio.

Referencias

[AKK99] Sanjeev Arora, David Karger y Marek Karpinski. Esquemas de aproximación de tiempo polinómico para casos densos de problemas NP-difíciles. Journal of Computer and System Sciences , 58 (1): 193–210, febrero de 1999. http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan y Mario Szegedy. Verificación de la prueba y la dureza de los problemas de aproximación. Journal of the ACM , 45 (3): 501–555, mayo de 1998. http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora y Shmuel Safra. Comprobación probabilística de pruebas: una nueva caracterización de NP. Journal of the ACM , 45 (1): 70–122, enero de 1998. http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige. Un umbral de ln n para aproximar la cobertura del conjunto. Journal of the ACM , 45 (4): 634–652, julio de 1998. http://doi.acm.org/10.1145/285055.285059

Tsuyoshi Ito
fuente
m=O(n)m=Ω(n3)
1
Ω(n2)Ω(nd)Ω(nd)
1
@ Tsuyoshi: Estoy ansioso por leer tu periódico.
András Salamon
44
sn1.5n1.9
77
MM3mM37/8+ϵNN2.999
Luca Trevisan

Respuestas:

6

an2ϵϵ

sϕN

Φ

  1. xiϕΦnyij
  2. iababΦyiayibyibyibyiayiayia=yib
  3. ϕxixjxkabΦxiyiaxjyjbxkyk(a+b)n

m=nNΦ2Nn253Nn2113Nn2n=Nkm=Nk+1C=113N2k+1=113m21k+1k=ϵ11Cm2ϵ

Φ

ϕ(1s)Nyiayiba,bn1(1s)Na,by:ay:by:(a+b)1s5N1s5N(n1)ab1s5Nn2=3(1s)11C(1s)Nn2=(1s)m2k+1k+1=(1s)Cs=4+s5

Las constantes probablemente necesitan ser verificadas dos veces.

Joe Fitzsimons
fuente
Gracias Joe. Lo siento si esto no estaba claro, pero en esta pregunta, requiero que las tres variables en cada cláusula sean todas distintas y, por lo tanto, no se pueden usar las cláusulas de comparación tal como están escritas. Tengo una prueba del mismo hecho (cláusulas limitadas por pares, Ω (n ^ (2 − ε)), con espacio) que usa gráficos expansores, pero si se puede probar sin usar expansores, estoy muy interesado.
Tsuyoshi Ito
yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)
ϵk=k(n)
Veré los detalles con más cuidado más adelante, pero la idea de usar a, by (a + b) parece funcionar. Esto debería liberarme de tratar explícitamente con los expansores. ¡Gracias!
Tsuyoshi Ito
No hay problema. Me alegro de poder ser de ayuda.
Joe Fitzsimons