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.

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 , there exists a pair of functions 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