NPhardness

NP-hardness is a central concept in computational complexity that describes the relative difficulty of problems. A problem H is NP-hard if every problem in NP can be transformed into H by a polynomial-time many-one reduction. In other words, an efficient algorithm for H would yield efficient algorithms for all problems in NP. NP-hardness concerns decision problems as well as optimization or search problems; the target problem H itself need not lie in NP.

NP-complete and the role of reductions: If a problem is both in NP and NP-hard, it is called NP-complete. NP-hard problems may lie outside NP, in which case they are at least as hard as the hardest problems in NP but not necessarily decidable within nondeterministic polynomial time. A standard way to compare problems is via polynomial-time reductions: A ≤p B means there exists a polynomial-time computable function that maps any instance x of A to an instance f(x) of B such that x is in A if and only if f(x) is in B. If any NP problem reduces to H, then H is at least as hard as the entire class NP.

Examples and implications: SAT, specifically 3-SAT, is NP-complete, so every problem in NP can be reduced to it. Many NP-hard problems arise as optimization versions of NP-complete problems (for example, the minimum-length traveling salesman problem) or as decision problems outside NP. In practice, NP-hardness explains why many real-world problems are tackled with heuristics, exact exponential-time algorithms for small instances, or approximation methods rather than guaranteed polynomial-time exact solutions.