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-hard, then P=NP.^[1]

Note that the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set.^[2] Mahaney's theorem was motivated by the Berman–Hartmanis conjecture

Given any two NP-complete sets ${\displaystyle A,B}$, there exists a pair of functions ${\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:^[3]

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.