Mahaney's theorem is a theorem in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
proven by Stephen Mahaney that states that if any
sparse language In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length ''n'' in the language, is bounded by a polynomial function of ''n''. They are ...
is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
, then P = NP. Also, if any sparse language is NP-complete with respect to
Turing reduction
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
s, then the
polynomial-time hierarchy collapses to
.
Mahaney's argument does not actually require the sparse language to be in NP, so there is a sparse
NP-hard set if and only if P = NP. This is because the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set.
References
{{compsci-stub
Computational complexity theory