DAA - Teorema de Cook

Stephen Cook presentó cuatro teoremas en su artículo "La complejidad de los procedimientos de demostración de teoremas". Estos teoremas se enuncian a continuación. Entendemos que se están utilizando muchos términos desconocidos en este capítulo, pero no tenemos ningún margen para discutir todo en detalle.

Los siguientes son los cuatro teoremas de Stephen Cook:

Teorema-1

Si un conjunto S de cadenas es aceptado por alguna máquina de Turing no determinista dentro del tiempo polinomial, luego S es P-reducible a {tautologías DNF}.

Teorema 2

Los siguientes conjuntos son P-reducibles entre sí en pares (y por lo tanto cada uno tiene el mismo grado de dificultad polinomial): {tautologías}, {tautologías DNF}, D3, {pares de sub-gráficos}.

Teorema 3

• Para cualquier T_Q(k) de tipo Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ no está acotado

• Hay un T_Q(k) de tipo Q tal que $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $

Teorema 4

Si el conjunto S de cadenas es aceptado por una máquina no determinista dentro del tiempo T(n) = 2ⁿ, y si T_Q(k) es una función de tipo honesta (es decir, contable en tiempo real) Q, entonces hay una constante K, entonces S puede ser reconocido por una máquina determinista en el tiempo T_Q(K8ⁿ).

• Primero, enfatizó la importancia de la reductibilidad del tiempo polinomial. Significa que si tenemos una reducción de tiempo polinomial de un problema a otro, esto asegura que cualquier algoritmo de tiempo polinomial del segundo problema se pueda convertir en un algoritmo de tiempo polinomial correspondiente para el primer problema.

• En segundo lugar, centró la atención en la clase NP de problemas de decisión que pueden resolverse en tiempo polinomial mediante una computadora no determinista. La mayoría de los problemas intratables pertenecen a esta clase, NP.

• En tercer lugar, demostró que un problema particular de NP tiene la propiedad de que todos los demás problemas de NP pueden reducirse polinomialmente a él. Si el problema de satisfacibilidad se puede resolver con un algoritmo de tiempo polinomial, entonces todos los problemas en NP también se pueden resolver en tiempo polinomial. Si algún problema en NP es intratable, entonces el problema de satisfacibilidad debe ser intratable. Por lo tanto, el problema de satisfacibilidad es el problema más difícil en NP.

• En cuarto lugar, Cook sugirió que otros problemas en NP podrían compartir con el problema de satisfacibilidad esta propiedad de ser el miembro más difícil de NP.