*** Welcome to piglix ***

Mahaney's theorem


Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP. Also, if there is a turing reduction from an NP-complete sparse set to P, then the polynomial time hierarchy collapses to ∆_2 (NP^{NP [logn]}).


...
Wikipedia

...