Teorema de Karp-Lipton
En la teoría de la complejidad , el teorema de Karp-Lipton establece que si el problema de satisfacibilidad booleano (SAT) puede resolverse mediante circuitos booleanos con un número polinomial de puertas lógicas, entonces
Es decir, si asumimos que NP , la clase de problemas de tiempo polinomial no determinista, puede estar contenida en la clase de complejidad de tiempo polinomial no uniforme P / poli , entonces esta suposición implica el colapso de la jerarquía polinomial en su segundo nivel. Se cree que tal colapso es poco probable, por lo que los teóricos de la complejidad generalmente ven el teorema como evidencia de la inexistencia de circuitos de tamaño polinomial para SAT o para otros problemas NP-completos . Una prueba de que tales circuitos no existen implicaría que P ≠ NP . Como P / poli contiene todos los problemas que se pueden resolver en tiempo polinomial aleatorio ( teorema de Adleman), el teorema de Karp-Lipton también es evidencia de que el uso de la aleatorización no conduce a algoritmos de tiempo polinomial para problemas NP-completos.
El teorema de Karp-Lipton lleva el nombre de Richard M. Karp y Richard J. Lipton , quienes lo probaron por primera vez en 1980. (Su demostración original colapsó PH a , pero Michael Sipser la mejoró ).
Las variantes del teorema establecen que, bajo el mismo supuesto, MA = AM y PH colapsa a SP
2clase de complejidad. Hay posibles conclusiones más sólidas si se supone que PSPACE , o algunas otras clases de complejidad, tienen circuitos de tamaño polinomial; ver P / poli . Si se supone que NP es un subconjunto de BPP (que es un subconjunto de P / poli), entonces la jerarquía polinomial colapsa a BPP . [1] Si se supone que coNP es un subconjunto de NP / poli , entonces la jerarquía polinomial colapsa a su tercer nivel.
Suponga que los circuitos de tamaño polinomial para SAT no solo existen, sino que también podrían construirse mediante un algoritmo de tiempo polinomial. Entonces, esta suposición implica que el propio SAT podría resolverse mediante un algoritmo de tiempo polinomial que construye el circuito y luego lo aplica. Es decir, los circuitos construibles de manera eficiente para SAT conducirían a un colapso más fuerte, P = NP.
La suposición del teorema de Karp-Lipton, de que estos circuitos existen, es más débil. Sin embargo, todavía es posible para un algoritmo en la clase de complejidad a adivinar un circuito correcto para SAT. La clase de complejidad describe problemas de la forma