Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that:
If any sparse language is NP-hard, then P = NP. Note that the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set. Mahaney's theorem was motivated by the Berman–Hartmanis conjecture:
Given any two NP-complete sets A , B {\displaystyle A,B} , there exists a pair of functions f : A → B , f − 1 : B → A {\displaystyle f:A\to B,f^{-1}:B\to A} that are mutual inverses of each other, and are computable in polynomial time. Since we know that some NP-complete sets are not sparse (for example, the set of satisfiable 3SAT formulas), Berman and Hartmanis derived a second, weaker conjecture:
There are no NP-complete sparse sets. Mahaney's result shows that, if P ≠ NP, then indeed there are no NP-complete sparse sets, thus settling the second conjecture under the standard assumption of P ≠ NP. The result was strengthened in 1991 to state that:
If there exists a sparse language, such that a polynomial-time algorithm exists to solve the SAT problem by making O(1) queries to the sparse language oracle, then P = NP. This is stronger than Mahaney's theorem, which is the special case where the polynomial-time algorithm can make at most 1 query to the sparse language protocol.
References