Teorema de Mahaney
El teorema de Mahaney es un teorema en la teoría de la complejidad computacional probado por Stephen Mahaney que establece que si cualquier lenguaje disperso es NP-completo , entonces P = NP. Además, si algún lenguaje disperso es NP-completo con respecto a las reducciones de Turing , entonces la jerarquía de tiempo polinomial colapsa a . [1]
