Teorema de Mahaney

El teorema de Mahaney es un teorema de la teoría de la complejidad computacional demostrado por Stephen Mahaney que establece que

Si algún lenguaje disperso es NP-difícil , entonces P=NP. ^{[ 1 ]}

Nótese que la existencia de un conjunto disperso NP-difícil implica la existencia de un conjunto disperso NP-completo. ^{[ 2 ]} El teorema de Mahaney fue motivado por la conjetura de Berman-Hartmanis.

Dados dos conjuntos NP-completos cualesquiera${\displaystyle A,B}$, existe un par de funciones${\displaystyle f:A\to B,f^{-1}:B\to A}$que son inversas mutuas entre sí y se pueden calcular en tiempo polinomial.

Dado que sabemos que algunos conjuntos NP-completos no son dispersos (por ejemplo, el conjunto de fórmulas 3SAT satisfacibles ), Berman y Hartmanis derivaron una segunda conjetura, más débil:

No existen conjuntos dispersos NP-completos.

El resultado de Mahaney muestra que, si P≠NP, entonces efectivamente no existen conjuntos dispersos NP-completos, resolviendo así la segunda conjetura bajo el supuesto estándar de P≠NP. El resultado se reforzó en 1991 para afirmar que: ^{[ 3 ]}

Si existe un lenguaje disperso, tal que existe un algoritmo de tiempo polinomial para resolver el problema SAT haciendo O(1) consultas al oráculo del lenguaje disperso, entonces P=NP.

Esto es más sólido que el teorema de Mahaney, que es el caso especial en el que el algoritmo de tiempo polinomial puede realizar como máximo 1 consulta al protocolo de lenguaje disperso.