P vs NP & Choosing an Algorithm

Some problems have no known fast algorithm, and spotting one early saves you days of hunting for a solution that probably does not exist. This lesson also closes the roadmap with a guide for picking the right tool.

advanced⏱ 15 min read

←Builds on

10Bitmask DPBitmask DP solves the salesman in O(2ⁿ·n²): better than n!, still exponential, which is what NP-hard looks like.100-1 Knapsack0-1 knapsack is NP-hard; its O(n·W) table is fast only while W stays small.8Minimum Spanning Tree: Kruskal & PrimAn MST gives a tour at most twice the optimum for metric TSP, a classic way to cope with hardness.

Leads to→

This is where the roadmap ends. Look back at how far you came.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Polynomial vs exponential

Every algorithm on this roadmap so far, from binary search to Dijkstra to LCS, runs in polynomial time: O(n), O(n log n), O(n²), O(n³). Doubling n multiplies the work by a constant (2, 4, 8).

Brute force over choices is different. Trying every subset costs 2ⁿ, every ordering n!. Here adding one element doubles the work (or worse). On a log scale the polynomials look almost flat, while 2ⁿ and n! shoot through the line of 10⁸ operations per second at n ≈ 27 and n ≈ 12.

A faster computer does not save you: one that is 1000 times faster lets a 2ⁿ algorithm handle only about 10 more elements. That is why computer scientists use "polynomial" as the working definition of efficient.

02P and NP: finding vs checking

Think of yes/no questions. P is the class we can *solve* in polynomial time: is there a path from s to t? Is this array sortable with k swaps?

NP is the class where a "yes" answer comes with a certificate we can *check* in polynomial time. Subset sum: "is there a subset of these numbers adding to 9?" Finding one may need 2ⁿ tries, but if someone hands you {4, 5}, you add two numbers and you are done. A sudoku is hard to fill and trivial to verify.

Every problem in P is also in NP: if you can solve it, you can check it. The famous open question is whether P = NP, that is, whether easy to check always means easy to find. Nobody has proved it either way. Most researchers believe P ≠ NP, and a proof would earn a prize of a million dollars.

03NP-complete problems and reductions

A reduction translates every instance of problem A into an instance of problem B, in polynomial time, so that the answers match. Then a fast solver for B would give a fast solver for A. In other words, B is at least as hard as A.

A problem is NP-complete if it is in NP and every NP problem reduces to it. These are the hardest problems in NP, and they stand or fall together: a polynomial algorithm for one would give one for all. Thousands are known, for example:

SAT: can these boolean clauses all be true at once?
TSP (decision): is there a tour of length ≤ L?
subset sum and its cousin, 0/1 knapsack
graph colouring with 3 colours, Hamiltonian path, clique

To show your problem is hard, reduce a known NP-complete problem to it, not the other way round.

04Hard does not mean hopeless

NP-complete describes the worst case for large n. Your real input may be friendlier. Check these, roughly in order:

Is n small? n ≤ 10: try all permutations. n ≤ 20: subsets, bitmask DP (TSP in O(2ⁿ·n²)), backtracking with pruning. n ≤ 40: meet in the middle, two halves of 2^(n/2)
Are the numbers small? Knapsack and subset sum run in O(n · W) with a DP table. This is *pseudo-polynomial*: fast when W is small, not when W = 10^18
Is the structure special? Colouring is easy on trees and bipartite graphs; many hard graph problems become DP on trees
Is "good enough" OK? Approximation algorithms come with guarantees: for TSP with ordinary distances, a tour built from the MST is at most twice the optimum. Heuristics (greedy, local search, SAT solvers) usually work very well in practice, just without a proof

05Which algorithm when: the whole roadmap on one page

A judge or a production budget gives you roughly 10⁸ simple operations per second. So read the constraints first. They tell you which complexity the problem expects, and the complexity points to the tool.

Then match the shape of the problem:

shortest path, unweighted → BFS; weights ≥ 0 → Dijkstra; negative edges → Bellman–Ford; all pairs, small n → Floyd
"minimum / count / best over choices" with overlapping subproblems → DP; a provably safe local choice → greedy
"is the answer ≥ x?" and the answer is monotone → binary search on the answer
many range queries → prefix sums or a segment tree; connectivity under merges → DSU
pattern in text → KMP / Z / hashing; huge powers or counts → fast power mod p

If nothing polynomial fits and n is tiny, it may well be NP-hard, and now you know what to do.

Read the constraint, pick the complexity, then the tool. Limits assume about 10⁸ simple operations per second.

Cost at a glance

Subset sum: brute forceO(2ⁿ·n)

Subset sum: check a certificateO(n)

Subset sum: meet in the middleO(2^(n/2)·n)

Subset sum: DP over sums (pseudo-poly)O(n·W)

TSP: bitmask DPO(2ⁿ·n²)

Remember

NP problems are easy to check given a certificate; NP-complete ones are the hardest of them, and no polynomial algorithm for them is known.
Facing one, exploit small n (bitmask DP, backtracking, meet in the middle), small numbers (pseudo-polynomial DP), special structure, approximation or heuristics.
Always read the constraints first: they reveal the complexity the problem wants, and that points to the right algorithm.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Compare the two counters: the search fills all 2ⁿ squares, the certificate check adds a handful of numbers. Then watch the time column explode as n grows.

Interactive visualizerfocus here, then space ← →

Set, target = 9

33441252

All 64 subsets (2^6) · checked: 0 / 64

solutionbeing checkedcheckednot yet

Subset sum: does some subset of {3, 34, 4, 12, 5, 2} add up to 9? With n = 6 numbers there are 2^6 = 64 subsets to try. Each square below is one subset (one bitmask).

Pseudocode

 1 // FIND: is there a subset with sum = target? 2 for mask in 0 .. 2^n - 1:              // 2^n candidates 3   if sum(subset(mask)) == target: found 4 // CHECK: someone hands you a subset (certificate) 5 s = 0; for x in certificate: s += x 6 return s == target                     // O(n) 7 // every extra element doubles the search

1 / 1

Check

Three questions. Pick an answer to see why.

Assign n ≤ 18 workers to n jobs at minimum total cost (any cost matrix). What fits best?

Which statement about NP is correct?

You find a polynomial reduction from SAT (NP-complete) to your problem X. What does that tell you?

Practice

Real problems to lock it in, easiest first.

CSESApple Division beginner↗LeetCodePartition Equal Subset Sum intermediate↗CSESChessboard and Queens intermediate↗LeetCodeShortest Path Visiting All Nodes advanced↗CSESMeet in the Middle advanced↗