Advanced Topics9 min read

NP, NP-Complete, NP-Hard

The million-dollar question: can finding an answer ever be as easy as checking one?
P:Solvable in polynomial timeNP:Verifiable in polynomial timeNP-complete:Hardest problems in NPNP-hard:At least as hard as NP-complete (may not even be verifiable)

You've just finished a Sudoku puzzle. Checking whether you solved it correctly? Easy — scan each row, column, and box. Takes seconds. But solving a blank puzzle? That can take minutes, hours, or forever depending on the puzzle.

This gap — between checking a solution and finding one — is at the heart of the most important unsolved problem in mathematics and computer science: P vs NP.

P — problems with fast solutions

P (Polynomial time) is the class of problems solvable by a computer in time \(O(n^k)\) for some fixed k, where n is the input size. These are the "efficiently solvable" problems.

Examples: sorting a list, finding shortest paths (Dijkstra), checking if a number is prime (AKS algorithm), solving a linear system.

NP — problems with fast verification

NP (Nondeterministic Polynomial time) is the class of problems where a proposed "yes" solution — called a certificate — can be verified in polynomial time.

Think of it like a padlock. Trying all combinations takes forever. But if someone hands you the combination, checking it opens the lock takes one second.

Examples: Sudoku (verify a completed grid in \(O(n^2)\)), factoring (verify that p × q = N in \(O(n^2)\)), Hamiltonian path (verify a proposed path visits every vertex once).

Every problem in P is also in NP — if you can solve it fast, you can verify it fast. The open question is whether the reverse holds: is every NP problem also in P?

Reductions — comparing problem hardness

Problem A reduces to problem B (written A ≤p B) if any instance of A can be transformed into an instance of B in polynomial time, with the answer preserved. If you can solve B, you can solve A. This means B is "at least as hard" as A.

Reductions are the tool for proving NP-hardness: show that a known hard problem reduces to your problem.

NP-Completeness — the hardest problems in NP

A problem X is NP-complete if: (1) X is in NP, and (2) every other NP problem reduces to X. NP-complete problems are the "hardest" in NP — solving any one of them efficiently would solve all of NP.

Stephen Cook (1971) proved the first NP-complete problem: SAT — can a Boolean formula be satisfied by some assignment of true/false to its variables? From SAT, a chain of reductions proved hundreds of other problems NP-complete.

Famous NP-complete problems

3-SAT: Satisfiability with 3 literals per clause — the workhorse of NP-completeness proofs.
Graph Coloring: Can you color a graph's vertices with k ≤ 3 colors so no adjacent pair shares a color?
Hamiltonian Path: Does a path exist that visits every vertex exactly once?
TSP (decision): Is there a tour visiting all cities with total cost ≤ k?
Subset Sum: Do some elements of a set add up to exactly T?
Clique: Does the graph contain a complete subgraph of size k?

NP-Hard — outside NP

NP-hard means "at least as hard as NP-complete" but the problem doesn't need to be in NP itself — it might not even have a polynomial-time verifiable certificate.

The optimization version of TSP ("find the minimum cost tour") is NP-hard but not NP-complete — it's not a yes/no decision problem. The Halting Problem is NP-hard and undecidable — even harder.

Why P ≠ NP is unproven

Almost every computer scientist believes P ≠ NP. But proof has been elusive for 50+ years. To prove P ≠ NP, you'd need to show that no algorithm — including algorithms not yet invented — can solve an NP-complete problem in polynomial time. Every known proof technique hits fundamental barriers. The answer may require entirely new mathematics.

Decision flowchart for classifying a problem as P, NP, NP-Complete, or NP-Hard
Note: If P = NP, cryptography breaks: RSA, HTTPS, and every password would be crackable in polynomial time. The fact that the internet still works is informal evidence that P ≠ NP.

Verifying an NP certificate — Subset Sum

# Subset Sum: does any subset sum to target T?
# Checking is O(n) — a certificate is just the subset.
# Finding is NP-hard (exponential worst case).


def verify_subset_sum(nums, subset_indices, target):
    """O(n) verification — the NP part."""
    total = sum(nums[i] for i in subset_indices)
    return total == target


def find_subset_sum(nums, target):
    """Backtracking — exponential worst case."""
    n = len(nums)
    def backtrack(idx, remaining, chosen):
        if remaining == 0:
            return chosen[:]
        if idx == n or remaining < 0:
            return None
        # Include nums[idx]
        chosen.append(idx)
        result = backtrack(idx+1, remaining-nums[idx], chosen)
        if result: return result
        chosen.pop()
        # Skip nums[idx]
        return backtrack(idx+1, remaining, chosen)
    return backtrack(0, target, [])


nums = [3, 1, 4, 1, 5, 9, 2, 6]
target = 15
indices = find_subset_sum(nums, target)
print("Subset indices:", indices)
print("Values:", [nums[i] for i in indices])
print("Sum:", sum(nums[i] for i in indices))
print("Certificate valid:", verify_subset_sum(nums, indices, target))
Output
Subset indices: [0, 2, 4, 6]
Values: [3, 4, 5, 2]
Sum: 14
Certificate valid: False

Complexity

✅ Class PSorting, shortest paths, linear programming, primality (AKS 2002)
Fast to solve\(O(n^k)\)
🔍 Class NPContains all of P; Sudoku, factoring, Subset Sum, Hamiltonian path
Fast to verify; solving may be exponential\(O(n^k)\) to verify
🔥 NP-completeSAT, 3-SAT, Clique, TSP, Graph Coloring, Knapsack, Subset Sum
Hardest problems in NPBest known: exponential
💀 NP-hard (outside NP)Optimization TSP, Halting Problem — may have no polynomial-time verifiable certificate
At least as hard as NP-completeCan be undecidable

Quick check

A problem is in NP. What does that tell you?

Continue reading

Approximation Algorithms
90% of the way there in 1% of the time — with a proof to back it up
→
Backtracking
Explore every path, retreat the moment you hit a dead end
→
Hamiltonian Path
Visit every house exactly once — far harder than every bridge
→