NPhard

NPhard, commonly written as NP-hard, is a classification in computational complexity theory used for decision problems. A problem is NP-hard if every problem in the class NP can be transformed into it by a polynomial-time reduction. This means that solving an NP-hard problem efficiently would enable solutions to all problems in NP in polynomial time. NP-hardness does not require the problem to be itself in NP; thus NP-hard problems may be decidable or undecidable.

The relationship to NP and NP-complete: NP-hard problems are not necessarily in NP. When an NP-hard problem is also in NP, it is called NP-complete. NP-complete problems are both as hard as the hardest problems in NP and verifiable in polynomial time given a solution certificate. NP-hard problems often arise in optimization contexts or as decision problems that are at least as difficult as any problem in NP.

Reductions and verification: The standard tool for proving NP-hardness is a polynomial-time many-one reduction from a known NP-hard or NP-complete problem to the target problem. If a known NP-complete problem can be reduced to a problem L in polynomial time, L is NP-hard. Conversely, showing a problem is NP-hard usually involves reducing a canonical NP-complete problem, such as SAT or 3-SAT, to it.

Examples and scope: The decision version of the traveling salesman problem (is there a tour with length at most B?) is NP-complete, while the optimization version (minimizing tour length) is NP-hard. Other classic NP-hard problems include various scheduling, knapsack, and graph-optimization problems. It is widely believed that no polynomial-time algorithm exists for NP-hard problems unless P equals NP, though many NP-hard problems admit efficient algorithms for special cases or provide effective heuristics and approximations.

History: The concept of NP-hardness, together with NP-completeness, was popularized by Cook, Karp, Garey, and Johnson in the 1970s, shaping a central part of computational complexity theory.