Search
Menu
Home
Sources
About
Contacts
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 there is a
Turing reduction
from an
NP-complete
sparse
language
to
P
, then the
polynomial-time hierarchy
collapses to
∆_2
.