NP-Hard Problem — Definition, Formula & Examples

An NP-Hard problem is a problem that is at least as hard as the hardest problems in NP — meaning every problem in NP can be reduced to it. NP-Hard problems may or may not have solutions that can be verified quickly, but no known algorithm solves them efficiently in all cases.

A decision or optimization problem $H$ is NP-Hard if for every problem $L \in \text{NP}$ , there exists a polynomial-time many-one reduction from $L$ to $H$ . Equivalently, $H$ is NP-Hard if some NP-Complete problem is polynomial-time reducible to $H$ . Note that $H$ need not itself belong to NP.

How It Works

To show a problem is NP-Hard, you take a problem already known to be NP-Hard (or NP-Complete) and construct a polynomial-time reduction to your target problem. This reduction transforms any instance of the known hard problem into an instance of the new problem such that the answer is preserved. If you succeed, you have proven that the new problem is at least as hard as the known one. The first NP-Complete problem, SAT, was established by the Cook–Levin theorem, and most subsequent NP-Hardness proofs chain reductions from it or from problems already reduced from SAT.

Example

Problem: Show that the Traveling Salesman Problem (optimization version) is NP-Hard by relating it to the Hamiltonian Cycle problem, which is known to be NP-Complete.

Step 1: Define the reduction: Given a graph

G = (V, E)

with

n

vertices, construct a complete weighted graph

G'

on the same vertex set. Assign edge weights: if

(u,v) \in E

, set

w(u,v) = 1

; otherwise, set

w(u,v) = n + 1

w(u,v) = \begin{cases} 1 & \text{if } (u,v) \in E \\ n+1 & \text{otherwise} \end{cases}

Step 2: Relate solutions: A Hamiltonian cycle exists in

G

if and only if the optimal TSP tour in

G'

has total cost exactly

n

. If no Hamiltonian cycle exists, every tour must use at least one edge of weight

n+1

, making the minimum tour cost greater than

n

\text{Optimal TSP cost} = n \iff G \text{ has a Hamiltonian cycle}

Step 3: Conclude NP-Hardness: The construction runs in polynomial time (building

O(n^2)

edges). Since solving TSP optimally would solve the NP-Complete Hamiltonian Cycle problem, TSP is NP-Hard.

Answer: The optimization version of TSP is NP-Hard because a polynomial-time solution to it would immediately solve the Hamiltonian Cycle problem, which is NP-Complete.

Why It Matters

Identifying a problem as NP-Hard tells algorithm designers to stop searching for an exact polynomial-time solution (unless P = NP) and instead pursue approximation algorithms, heuristics, or special-case solutions. This classification directly impacts fields like logistics, scheduling, cryptography, and machine learning, where NP-Hard problems appear routinely.

Common Mistakes

Mistake: Assuming every NP-Hard problem is in NP.

Correction: NP-Hard means 'at least as hard as NP,' but the problem itself may not be in NP. For example, the Halting Problem is NP-Hard but undecidable, so it is not in NP. A problem that is both NP-Hard and in NP is called NP-Complete.