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 language to P, then the polynomial-time hierarchy collapses to ∆_2 (NP^{NP [logn]}).[1]

References
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.