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 any sparse language is NP-complete with respect to Turing reductions, then the polynomial-time hierarchy collapses to

[1] Mahaney's argument does not actually require the sparse language to be in NP, so there is a sparse NP-hard set if and only if P = NP.

This is because the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set.

[2] This computer science article is a stub.