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 $\Delta _{2}^{P}$ .[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

Mahaney, Stephen R. (October 1982). "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis". Journal of Computer and System Sciences. 25 (2): 130–143. doi:10.1016/0022-0000(82)90002-2. hdl:1813/6257.
Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Springer. pp. 130–131. ISBN 3-540-52079-1.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Mahaney, Stephen R. (October 1982). "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis". Journal of Computer and System Sciences. 25 (2): 130–143. doi:10.1016/0022-0000(82)90002-2. hdl:1813/6257.

[2] Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Springer. pp. 130–131. ISBN 3-540-52079-1.