NemoClaw Knowledge Wiki

np-hard

2 min read

🗂️ Maths, Logic & Crypto · View mindmap

NP Hard

NP-hard is a classification in computational complexity theory that identifies problems at least as difficult as the hardest problems in NP (nondeterministic polynomial time). A problem is formally NP-hard if every problem in NP can be reduced to it in polynomial time. This means that discovering a polynomial-time algorithm for any single NP-hard problem would immediately yield polynomial-time solutions for all problems in NP, effectively proving P = NP.

Key Properties

NP-hard problems do not necessarily belong to NP themselves. While NP problems must have solutions verifiable in polynomial time, NP-hard problems may be verification-hard or even undecidable. An NP-hard problem that also belongs to NP is classified as NP-complete, representing the intersection of these two categories. The hardness designation depends only on the existence of a polynomial-time reduction from all NP problems, not on whether solutions can be verified efficiently.

Examples and Significance

Common NP-hard problems include the traveling salesman problem, the knapsack problem, and satisfiability (SAT). These problems are computationally challenging in practice, with no known polynomial-time solutions despite decades of research. The widespread assumption that P ≠ NP means NP-hard problems likely require exponential time in the worst case, making them practically intractable for large instances. This classification guides algorithm research toward approximation algorithms, heuristics, and specialized approaches rather than seeking exact polynomial solutions.

Source Notes

Graph View

Backlinks