Mahaney's theorem
id:
mahaney-s-theorem-262-8592562
title:
Mahaney's theorem
text:
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 any sparse language is NP-complete with respect to Turing reductions, then the polynomial-time hierarchy collapses to Δ 2 P . 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 exi
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Mahaney%27s_theorem
date created:
date modified:
2022-10-27T02:49:17Z
main entity:
{"identifier":"Q20707135","url":"https://www.wikidata.org/entity/Q20707135"}
image:
fields total:
13
integrity:
13