마하니의 정리

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]

참조

  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.
Stub icon

이 컴퓨터 과학 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.