¿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?

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 ₁ ∨ x ₂ ∨ x ₄ ) ∧ (￢x ₁ ∨￢x ₃ ∨ x ₄ ) ∧ ( x ₁ ∨ x ₃ ∨￢x ₅ ) está emparejada en 2 pero no está emparejada en pares 1 limitado porque, por ejemplo, el par ( x ₁ , x ₄ ) 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 ² cláusulas, donde n es el numero de variables?

La delimitación por pares implica claramente que solo hay cláusulas O ( n ² ). 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 ³ ) [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

$an^{2-\epsilon}$$\epsilon$

$_s$$\phi$$N$

$\Phi$

1. $x_i$$\phi$$\Phi$$n$$y_{ij}$
2. $i$$a$$b$$a\neq b$$\Phi$$y_{ia}∨￢y_{ib}∨￢y_{ib}$$y_{ib}∨￢y_{ia}∨￢y_{ia}$$y_{ia} = y_{ib}$
3. $\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$

$m = nN$$\Phi$$2Nn^2$$\frac{5}{3}Nn^2$$\frac{11}{3}Nn^2$$n = N^k$$m = N^{k+1}$$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}$

$\Phi$

$\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)}$$\frac{1-s}{5}N$$\frac{1-s}{5}N(n-1)$$a$$b$$\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}$

Las constantes probablemente necesitan ser verificadas dos veces.