KnowraNP-completenessLinked fromLinked fromThe 22 pages that link to NP-completeness, each with the reason it gives.All 22Broader topic 3Related 10Narrower topic 7Compared with 2P versus NP problemRelated: An NP-complete problem in P would establish P = NP.Polynomial-time reductionRelated: Polynomial-time reductions are the standard tool for proving NP-hardness.SAT solverRelated: SAT's NP-completeness explains why no general efficient algorithm is known.Many-one reductionRelated: Many-one reductions are the standard tool for proving NP-hardness and completeness.NP-hardnessRelated: It adds membership in NP to the hardness property.Polynomial timeRelated: A polynomial-time algorithm for any NP-complete problem would give polynomial-time algorithms for all problems in NP.Stephen CookRelated: Cook introduced this framework through his theorem, making it central to complexity theory.Travelling salesman problemRelated: The decision version is NP-complete, linking tour existence to the central complexity class.Stable roommates problemRelated: Many variants of stable matching become computationally hard even when the classical problem is tractable.Theory of computationRelated: It identifies problems whose efficient solution would yield efficient solutions for all NP problems.