Complejidades de tiempo de los solversadores de vanguardia de la técnica con respecto a la longitud de la fórmula

Question

Estoy aprendiendo sobre los solversadores SAT DPLL y CDCL, y sé que tienen complejidad de tiempo exponencial al número de variables.

Si no me equivoco, una de las razones por las que la mayoría cree que P no es igual a NP es que no existe un algoritmo de tiempo polinomial para sentarse a pesar del tremendo esfuerzo de matemáticos y científicos informáticos. Sin embargo, el problema de P VS NP solo se preocupa por la complejidad del tiempo con respecto a la longitud de la fórmula, no el número de variables.

Si estos solversadores de vanguardia se ejecutaron en fórmulas 3CNF, una complejidad de tiempo exponencial al número de variables implica una complejidad de tiempo exponencial a la longitud del 3CNF.

Sin embargo, si se ejecutaron en CNF arbitrarios, cuya longitud puede ser exponencial al número de variables, entonces una complejidad de tiempo exponencial al número de variables no implicaría necesariamente una complejidad de tiempo exponencial a la longitud de la CNF.

Por lo tanto, una pregunta relacionada es, ¿se ejecutan estos solversadores SAT en 3CNF o CNF al tiempo que mide la complejidad del tiempo?

Answer 1

Para 3SAT, el número de variables se relaciona de polinómicamente con el número de cláusulas. (Vea el final para la justificación.)

En consecuencia, cualquier algoritmo para 3SAT cuyo tiempo de funcionamiento es polinomio en el número de cláusulas también sería polinomio en el número de variables; y cualquier algoritmo para 3SAT cuyo tiempo de funcionamiento es polinomio en el número de variables también sería polinomial en el número de cláusulas.

Se sabe que hay un algoritmo de tiempo polinomial para 3SAT, si y solo si hay un algoritmo de tiempo polinomial para SAT, si y solo si hay un algoritmo de tiempo polinomial para Circuitsat (por ejemplo, para fórmulas) . Además, a pesar de las décadas de trabajo en los solucionadores SAT, nadie conoce ningún algoritmo para 3SAT que se ejecuta en tiempo polinomial (o, de hecho, en tiempo menos que exponencial en el peor de los casos). Podría tomar esto como evidencia de que no hay algoritmo de tiempo polinómico para 3SAT; lo que implica que no existe un algoritmo de tiempo polinómico para SAT o CIRCUSAT, tampoco, y también implica que P!= NP.

---

Justificación: Deje que $ n $ denote el número de variables y $ m $ el número de cláusulas . Tenemos $ n \ le 3m $ (una variable que no aparece en ninguna cláusula se puede ignorar) y $ m \ le 8n ^ 3 $ (Cada cláusula tiene tres literales, y puede ignorar las cláusulas repetidas). Sigue que $ n / 3 \ le m \ le 8n ^ 3 $ y $ \ sqrt [3] {m / 8} \ le n \ le 3m $ , es decir, cada uno está relacionado de forma polinomial con la otra.

---

Veo que revisaste tu pregunta. Eso aclara que creo que tienes un error. Hablas de "Ejecutar [Ning] [un solucionador SAT] en fórmulas booleanas arbitrarias". Sin embargo, no puede ejecutar un Satver Satver en una fórmula booleana arbitraria. Los solucionadores SAT solo trabajan en fórmulas CNF.

Sin embargo, sí sabemos que cualquier fórmula booleana se puede convertir a una fórmula de tamaño de CNF equisatable en la mayoría polinomial en el tamaño de la fórmula, y viceversa. Si tuvo un algoritmo que podría probar la satisfacción de las fórmulas booleanas arbitrarias en el tiempo polinomial en el tamaño de la fórmula, entonces seguiría que tiene un algoritmo que podría probar la satisfacción de las fórmulas 3CNF en el tiempo polinomial en el tamaño de la fórmula (cada La fórmula 3CNF es una fórmula booleana), y por lo tanto un algoritmo que podría probar la satisfacción de las fórmulas de 3CNF en el tiempo polinomial en el número de variables, lo que contradice la evidencia disponible. Entonces, si cree que no hay algoritmo para resolver 3SAT en tiempo polinomial en el número de variables, también debe creer que no hay algoritmo para probar la satisfacción de las fórmulas booleanas arbitrarias en el tiempo polinomial en el tamaño de la fórmula. < / p>