Linked from

The 22 pages that link to NP-completeness, each with the reason it gives.

• Graph coloringNarrower topic: Deciding whether a graph is 3-colorable is NP-complete.

• Computational complexity theoryBroader topic: An efficient algorithm for any NP-complete problem would imply P equals NP.

• P 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.

• Graph isomorphismCompared with: Graph isomorphism is not known to be NP-complete, unlike many familiar hard problems.

• Many-one reductionRelated: Many-one reductions are the standard tool for proving NP-hardness and completeness.

• Cook–Levin theoremNarrower topic: The theorem's conclusion combines hardness with efficient verification.

• 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.

• Leonid LevinNarrower topic: Levin independently established foundational completeness results, alongside Stephen Cook.

• Stephen CookRelated: Cook introduced this framework through his theorem, making it central to complexity theory.

• Fixed-parameter tractabilityCompared with: Classical NP-hardness alone does not determine whether a problem is fixed-parameter tractable for a chosen parameter.

• Hamiltonian cycleNarrower topic: Hamiltonian-cycle existence is NP-complete, making efficient general solutions unlikely.

• Nondeterministic Turing machineBroader topic: NP-complete problems capture the hardest cases associated with polynomial-time nondeterminism.

• Hamiltonian path problemNarrower topic: The general Hamiltonian path decision problem is NP-complete.

• Theoretical computer scienceBroader topic: It is established through reductions and captures a central unresolved boundary.

• Travelling salesman problemRelated: The decision version is NP-complete, linking tour existence to the central complexity class.

• Clique problemNarrower topic: The decision version of clique is a canonical NP-complete problem.

• 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.

• Richard M. KarpNarrower topic: Karp’s results helped turn this complexity classification into a central tool.