Encuentra st es -duro para cualquier

Deje que $L_\epsilon$ sea ​​el lenguaje de todas las fórmulas $2$ -CNF $\varphi$ , de modo que pueda satisfacerse al menos $(\frac{1}{2}+\epsilon)$ de las cláusulas de $\varphi$ .

Necesito demostrar que existe $\epsilon'$ st $L_\epsilon$ es $\mathsf{NP}$ -hard para cualquier $\epsilon<\epsilon'$ .

Sabemos que $\text{Max}2\text{Sat}$ puede ser aproximado a $\frac{55}{56}$ precedente de las cláusulas de una reducción de $\text{Max}3\text{Sat}$ . ¿Cómo debería resolver este?

En su famoso artículo, Håstad muestra que es NP-difícil aproximar MAX2SAT mejor que $21/22$ . Esto probablemente significa que es NP-difícil de distinguir instancias que son $\leq \alpha$ satisfactorias e instancias que son $\geq (22/21) \alpha$ satisfactorias, para algunos $\alpha \geq 1/2$ . Ahora imagine rellenar una instancia para que se convierta en una fracción $p$ de una nueva instancia, el resto de la cual es exactamente $1/2$ satisfactoria (digamos que consiste en grupos de cláusulas de la forma $a \land \lnot a$ ). Los números ahora se convierten en $1/2 + p (\alpha - 1/2)$ y 1 /$1/2 + p((22/21)\alpha - 1/2)$. El último número se puede hacer tan cerca de como queramos.$1/2$

Si sabe que ε es un número racional, entonces no necesita una aproximación para que Max-2-SAT pruebe su afirmación. Una prueba típica de la dureza NP de Max-2-SAT (por ejemplo, la del libro de texto Complejidad computacional de Papadimitriou) demuestra en realidad la integridad NP de L _1/5 . Para probar la NP-dureza de L _ε para positivo números racionales ε <1/5, podemos reducir L _1/5 a L _ε como sigue: dado un fórmula 2CNF φ (una instancia para L _1/5 ), deja que m sea El número de cláusulas en él. Deje r ys ser números enteros positivos de modo que (1 / 5− ε ) mr = 2 ε s se mantenga. Luego construya una fórmula 2CNF (una instancia para L _ε ) repitiendo φ por r veces y agregando s pares de cláusulas contradictorias. Un cálculo simple muestra que esto es realmente una reducción de L _1/5 a L _ε .

Esta reducción claramente funciona solo si ε es racional, porque de lo contrario r y s no pueden tomarse como enteros. El caso general donde ε no es necesariamente racional parece requerir una aproximación, como Yuval Filmus escribió en su respuesta.