Mahaney's theorem
Mahaney's theorem is a theorem in
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]
References
- hdl:1813/6257.
- ISBN 3-540-52079-1.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |