Hard problems: P, NP and approximation

Every algorithm so far ran in polynomial time: O(n), O(n log n), O(n³). Some problems that look just as innocent have no known polynomial algorithm at all. Recognising them saves you from hunting for a clever solution that probably does not exist, and points you to the techniques that work instead.

P and NP in plain words

• P is the class of yes/no problems that can be solved in polynomial time. Is there a route of at most 40 km from the yard to the site? Dijkstra answers that.
• NP is the class of yes/no problems where a proposed answer can be checked in polynomial time. Is there a round trip through all 20 sites of at most 100 km? Hard to find, but if someone hands you a round, you can add up its length in O(n) and check.
• Every problem in P is in NP (if you can solve it, you can check an answer). The great open question, P = NP?, asks whether every quickly checkable problem is also quickly solvable. Most researchers believe not, and a proof either way is worth a US$1 million Millennium Prize.

1int[] loads = { 34, 4, 12, 5, 2, 27, 19, 8 };        // can a truck carry exactly 50?2int target = 50;3 4int[] claim = { 0, 1, 2 };                           // someone claims: 34 + 4 + 125Console.WriteLine($"Claim checked: {claim.Sum(i => loads[i]) == target}");   // O(n)6 7int solutions = 0;8for (int mask = 0; mask < 1 << loads.Length; mask++) // finding one ourselves: every subset, 2^n9{10    int sum = 0;11    for (int i = 0; i < loads.Length; i++)12        if ((mask & (1 << i)) != 0) sum += loads[i];13    if (sum == target) solutions++;14}15Console.WriteLine($"Searched {1 << loads.Length} subsets, {solutions} hit {target}");

Claim checked: True
Searched 256 subsets, 4 hit 50

Checking took 3 additions. Searching took 256 subsets for 8 loads; for 60 loads it would be 2⁶⁰ ≈ 10¹⁸. That gap between checking and finding is the heart of NP.

NP-complete: the hardest of them

A problem is NP-complete if it is in NP and every other NP problem can be reduced to it: translated in polynomial time into an instance of it. So a fast algorithm for any single NP-complete problem would give fast algorithms for all of them. Thousands are known, among them travelling salesman (the yes/no version), subset sum, 0/1 knapsack, graph colouring, scheduling with deadlines, Sudoku on n × n boards, and SAT, the first one proved (Cook, 1971). Problems at least this hard but not necessarily yes/no, such as “find the shortest round”, are called NP-hard.

Exact for small n, good enough for large n

Here is travelling salesman with real numbers. The exact method tries every round; the greedy nearest-neighbour method and the 2-opt local search are approximations. Add sites and watch the exact work explode while the approximations stay close:

When a problem is NP-hard, you have several practical options:

1. Small inputs: exact search. Brute force or backtracking with pruning handles n ≤ 10–12. Bitmask DP (Held-Karp for TSP) is O(n²·2ⁿ), good up to about 20–25.
2. Small numbers: pseudo-polynomial DP. 0/1 knapsack is O(n·W): fast when the capacity W is a few thousand, even though it is exponential in the number of digits of W.
3. Approximation with a guarantee. Some algorithms promise to be within a factor of the optimum: the vertex cover method below is at most 2× optimal; Christofides’ algorithm for TSP with real distances is at most 1.5×.
4. Heuristics and local search. Greedy construction plus improvement (2-opt, simulated annealing, genetic algorithms) gives excellent answers in practice with no guarantee.
5. Special structure. The general problem is hard, but yours may not be: colouring is easy on trees, many problems are polynomial on graphs with small treewidth.
6. Solvers. SAT solvers and integer linear programming solvers (such as Google OR-Tools) solve industrial instances with thousands of variables.

1int[,] d =                                          // driving minutes between the yard (0) and 4 sites2{3    { 0, 12, 10, 19, 8 },4    { 12, 0, 3, 7, 2 },5    { 10, 3, 0, 6, 20 },6    { 19, 7, 6, 0, 4 },7    { 8, 2, 20, 4, 0 }8};9int n = d.GetLength(0), full = 1 << n, inf = int.MaxValue / 2;10var best = new int[full, n];                        // best[set, j]: shortest path from 0 visiting set, ending at j11for (int s = 0; s < full; s++) for (int j = 0; j < n; j++) best[s, j] = inf;12best[1, 0] = 0;13 14for (int s = 1; s < full; s += 2)                   // every set containing the yard (bit 0)15    for (int j = 0; j < n; j++)16    {17        if ((s & (1 << j)) == 0 || best[s, j] == inf) continue;18        for (int k = 0; k < n; k++)19            if ((s & (1 << k)) == 0)                // extend the path to a new site k20            {21                int t = s | (1 << k);22                best[t, k] = Math.Min(best[t, k], best[s, j] + d[j, k]);23            }24    }25 26int answer = inf;27for (int j = 1; j < n; j++) answer = Math.Min(answer, best[full - 1, j] + d[j, 0]);28Console.WriteLine($"Shortest round: {answer} minutes");29Console.WriteLine($"DP states: {full * n}, brute-force orders: {Factorial(n - 1)}");30 31static long Factorial(int k) => k <= 1 ? 1 : k * Factorial(k - 1);

Shortest round: 32 minutes
DP states: 160, brute-force orders: 24

For 5 places brute force is smaller, but the growth is what matters: at n = 20, brute force needs 19! ≈ 1.2 × 10¹⁷ orders while Held-Karp needs about 20² · 2²⁰ ≈ 4 × 10⁸ steps. Still exponential, but feasible.

An approximation with a guarantee

A vertex cover picks junctions so that every corridor has a guard at one end or the other; we want as few guards as possible (NP-hard). The simple rule “find a corridor with no guard and put guards at both ends” is never more than twice the optimum: the corridors it picks share no ends, and any cover needs at least one guard on each of them.

1var corridors = new[] { ("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "E"), ("D", "E"), ("D", "F") };2 3var cover = new HashSet<string>();4foreach (var (u, v) in corridors)5    if (!cover.Contains(u) && !cover.Contains(v)) { cover.Add(u); cover.Add(v); }   // guard both ends6Console.WriteLine($"2-approximation: {string.Join(", ", cover.Order())} ({cover.Count})");7 8var junctions = corridors.SelectMany(c => new[] { c.Item1, c.Item2 }).Distinct().ToArray();9int best = junctions.Length;10string bestSet = "";11for (int mask = 0; mask < 1 << junctions.Length; mask++)   // exact: try every subset12{13    var set = junctions.Where((_, i) => (mask & (1 << i)) != 0).ToHashSet();14    if (set.Count < best && corridors.All(c => set.Contains(c.Item1) || set.Contains(c.Item2)))15    {16        best = set.Count;17        bestSet = string.Join(", ", set.Order());18    }19}20Console.WriteLine($"Optimal: {bestSet} ({best})");

2-approximation: A, B, C, D, E, F (6)
Optimal: A, C, D (3)

Here the approximation hits its worst case exactly: 6 guards against an optimum of 3. Usually it does better, but the guarantee is what lets you trust it on inputs too large to check.

1int[,] d =2{3    { 0, 12, 10, 19, 8 },4    { 12, 0, 3, 7, 2 },5    { 10, 3, 0, 6, 20 },6    { 19, 7, 6, 0, 4 },7    { 8, 2, 20, 4, 0 }8};9int n = d.GetLength(0), here = 0, total = 0;10var visited = new bool[n];11visited[0] = true;12var route = new List<int> { 0 };13for (int step = 1; step < n; step++)14{15    int next = -1;16    for (int k = 0; k < n; k++)17        if (!visited[k] && (next < 0 || d[here, k] < d[here, next])) next = k;18    total += d[here, next];19    visited[next] = true;20    route.Add(next);21    here = next;22}23total += d[here, 0];                                 // drive back to the yard24route.Add(0);25Console.WriteLine($"{string.Join(" -> ", route)}: {total} minutes (optimum 32)");

0 -> 4 -> 1 -> 2 -> 3 -> 0: 38 minutes (optimum 32)