KnowraNP-hardnessLinked fromLinked fromThe 12 pages that link to NP-hardness, each with the reason it gives.All 12Broader topic 1Related 10Narrower topic 1NP-completenessBroader topic: This is the hardness half of the definition; it does not require the problem itself to lie in NP.Combinatorial optimizationRelated: Many general combinatorial optimization problems resist known polynomial-time exact algorithms.Polynomial-time reductionRelated: A reduction from an NP-hard problem transfers its hardness to the target.Approximation algorithmRelated: It explains why efficient approximation can matter when exact optimization is impractical.Many-one reductionRelated: A reduction from an NP-hard problem transfers its difficulty to the target.Chromatic numberRelated: Computing a graph’s chromatic number is NP-hard, limiting efficient exact methods.Cook–Levin theoremRelated: The reduction establishes this property for satisfiability.Vehicle routing problemRelated: The general routing problem resists known algorithms that guarantee exact solutions quickly as instances grow.Hamiltonian pathRelated: Optimization variants, including finding a longest path, are NP-hard.Sliding puzzleNarrower topic: Generalized sliding-puzzle solving is computationally hard as board size grows.Travelling salesman problemRelated: The optimization version is NP-hard, so efficient exact algorithms are not known in general.PCP theoremRelated: The theorem converts proof verification into strong hardness results through reductions.