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 2Graph coloringNarrower topic: Deciding whether a graph is 3-colorable is NP-complete.Cook–Levin theoremNarrower topic: The theorem's conclusion combines hardness with efficient verification.Leonid LevinNarrower topic: Levin independently established foundational completeness results, alongside Stephen Cook.Hamiltonian cycleNarrower topic: Hamiltonian-cycle existence is NP-complete, making efficient general solutions unlikely.Hamiltonian path problemNarrower topic: The general Hamiltonian path decision problem is NP-complete.Clique problemNarrower topic: The decision version of clique is a canonical NP-complete problem.Richard M. KarpNarrower topic: Karp’s results helped turn this complexity classification into a central tool.