Condiciones para la trazabilidad de 3SAT-Satisfiability

Lo que me pregunto específicamente es si existe una condición interesante en el porcentaje de asignaciones que satisfacen una fórmula 3SAT para garantizar que tales problemas sean manejables.

Supongamos, por ejemplo, la clase de problemas 3SAT que de las asignaciones posibles satisfacen la fórmula booleana; ¿podemos encontrar eficientemente una tarea satisfactoria? ¿Para qué es el problema resultante en P? $\epsilon(n) 2^n$ $2^n$ $\epsilon$

Editar nota: reemplazado con para aclarar la confusión. $\epsilon$ $\epsilon(n)$

cc.complexity-theory ds.algorithms sat np Rafi Witten
fuente

Una observación simple: si

es polinomialmente inverso como mínimo, entonces el muestreo uniforme

veces dará una solución en el tiempo polinomial esperado. Entonces, si

está entre 1 y 1 / poli (n), este problema es fácil (está en ZPP).

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

ϵ

$\epsilon$

Robin Kothari

Del mismo modo, si 1 / EPS es quasipolynomial, entonces usted tiene un algoritmo de tiempo quasipoly aleatorio, que a su vez sería sorprendente

Suresh Venkat

Respuestas:

$0< \epsilon <1$ $1/\textit{polylog}(n)$ $\epsilon 2^n$

Los algoritmos no son difíciles:

$S$ $S$

$\epsilon$

$S$ $S$ $S$

Creo que el algoritmo para 2SAT ya está en el famoso artículo de 1971 de S. Cook.

El algoritmo para 3CNF es de: L. Trevisan Una nota sobre conteo aproximado determinista para k-DNF en el proceso. de APROX-RANDOM, Springer-Verlag, página 417-426, 2004

El documento original que muestra el resultado para 3CNF es: E. Hirsch, un algoritmo determinista rápido para fórmulas que tienen muchas tareas satisfactorias , Journal of the IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
fuente

ϵ

$\epsilon$

ϵ = 1 / p o l y l o g (n)

$\epsilon = 1/polylog(n)$

¿Cómo se construye S?

Radu GRIGore

C_{1}

$C_1$

C_{2}

$C_2$

C_{1}

$C_1$