P, NP and Hard Problems: What to Say in an Interview

"P versus NP" sounds like theory, but interviewers use it for a practical reason. They want to see if you can tell a problem that has a clever fast solution from one that will run forever as the input grows, and what a senior engineer does in the second case. The wrong answers are on both sides: spending an hour hunting for a fast exact algorithm that almost certainly does not exist, or saying "NP-hard, impossible" and giving up.

This lesson gives the vocabulary in plain words, a list of well-known hard problems, how to notice one, and a set of runnable comparisons: brute force, DP, backtracking, greedy and approximation on the same inputs. Big-O is explained in DSA Lesson 12. The solving techniques appear in DSA Lesson 34, Backtracking, DSA Lesson 47, Greedy Algorithms and DSA Lesson 56, 2-D Dynamic Programming, where 0/1 knapsack and partition equal subset sum are covered.

Words used in this lesson

• Decision problem is a question with a yes/no answer, such as "is there a subset that sums to 100?". An optimisation problem asks for the best answer, such as "find the cheapest tour".
• P is the set of decision problems that a normal computer can solve in polynomial time: the steps grow like n^2 or n^3 (n to a fixed power) as the input size n grows. Sorting, shortest path and "is this number in the list" are in P.
• NP is the set of decision problems where, if someone gives you a "yes" answer with a proof (called a certificate), you can check the proof in polynomial time. It does not mean "not polynomial". Every problem in P is also in NP.
• NP-hard means "at least as hard as every problem in NP". An NP-hard problem does not have to be in NP itself.
• NP-complete means both: in NP, and NP-hard. These are the hardest problems in NP, and they are all equally hard: a fast solution to one would give a fast solution to all.
• Reduction means turning problem A into problem B so that a solver for B also solves A. It is how you prove one problem is as hard as another.
• Exponential time means the steps grow like 2^n or n!. Adding one item doubles (or more) the work.
• Pseudo-polynomial means polynomial in the size of the numbers, not in the number of digits needed to write them.
• Approximation algorithm is a fast algorithm with a proven limit on how far its answer can be from the best one (for example "never more than twice the best").
• Heuristic is a method that usually gives a good answer, with no proof about how good.

P, NP and the open question, in plain words

Two things are very different: finding an answer and checking an answer. Sudoku is a good picture. Solving a hard Sudoku is hard work. Checking a finished one takes seconds. NP is the class of problems where the checking is fast. P is the class where the finding is fast too.

The open question: is every problem whose answer is quick to check also quick to find? In other words, does P equal NP? Almost everyone believes the answer is no, but nobody has proved it. It is an open problem. If you are asked in an interview, "I believe P is not NP but it is unproven" is correct, and "it is proven that NP-complete problems need exponential time" is wrong.

Here is the "easy to check" idea in code. Checking a proposed subset takes a loop; finding one means searching:

const verifySubset = (nums, idx, target) => idx.reduce((s, i) => s + nums[i], 0) === target;const nums = [3, 34, 4, 12, 5, 2];console.log("verify certificate [index 2 and 5]:", verifySubset(nums, [2, 5], 6), "(4 + 2 = 6)");

verify certificate [index 2 and 5]: true (4 + 2 = 6)

A short list of famous hard problems

Reductions: why they are all "the same hard problem"

A reduction converts one problem into another. If you can turn every SAT question into a graph-colouring question quickly, then a fast colouring solver would solve SAT fast too. So colouring is at least as hard as SAT. That is how a list of thousands of problems got proved NP-complete: start from SAT, and chain reductions.

A small reduction you can check yourself: in a graph, a set of nodes is a vertex cover exactly when the nodes left out form an independent set (no two of them are joined by an edge). So minimum vertex cover + maximum independent set = n. I tested this by brute force on 200 random graphs:

const vcBrute = (n, E) => { let best = n; for (let mm = 0; mm < 2 ** n; mm++) { if (E.every(([u, v]) => mm >> u & 1 || mm >> v & 1)) { let c = 0; for (let x = mm; x; x &= x - 1) c++; best = Math.min(best, c); } } return best; };const isBrute = (n, E) => { let best = 0; for (let mm = 0; mm < 2 ** n; mm++) { if (E.every(([u, v]) => !(mm >> u & 1 && mm >> v & 1))) { let c = 0; for (let x = mm; x; x &= x - 1) c++; best = Math.max(best, c); } } return best; };let ok = 0; for (let t = 0; t < 200; t++) { const n = randInt(3, 12), E = edgesOf(n, 0.3); if (vcBrute(n, E) + isBrute(n, E) === n) ok++; } console.log("min vertex cover + max independent set = n in", ok, "of 200 graphs");

min vertex cover + max independent set = n in 200 of 200 graphs

(randInt and edgesOf are my small helpers: a seeded random integer, and a random graph where each pair of nodes has an edge with a given chance.) So a fast algorithm for one problem gives a fast algorithm for the other. Both are hard.

How to recognise "this is probably NP-hard"

Look for these signs in a problem statement:

1. The answer is a best subset, ordering, assignment or partition of the input, and the number of candidates is 2^n or n!.
2. You need to satisfy many constraints at once: schedule everyone with no clash, fit all items in the fewest boxes, colour a map with few colours.
3. A greedy rule seems natural but you can quickly find a counter-example. Each of your first two ideas breaks on a small case.
4. It is a famous problem in disguise. "Route a truck through all stops" is TSP. "Split the team so both halves have equal skill" is partition (a form of subset sum). "Pick the fewest servers so each link touches one" is vertex cover. "Assign time slots with no clashes" is colouring.
5. Small limits in the statement. If n is up to 20, or 40, the intended solution is usually exponential. If n is up to 100,000, there must be a polynomial (usually near-linear) solution, or the problem is not the hard version.

Also remember that small changes can move a problem from P to NP-complete. Shortest path is easy, but longest simple path is hard. 2-colouring is easy, 3-colouring is hard. 2-SAT is easy, 3-SAT is hard. Do not say "NP-hard" before you have checked that it is not just a known easy variant. And do not rely on a feeling: either find a reduction, or recognise a standard problem.

What to do when the problem is hard

The honest answer has layers. In order:

1. Check the input size. Small n means exponential algorithms are fine.
2. Check for structure. Special cases (a tree, planar graph, small numbers, small width) are often easy.
3. Exact algorithms that are smarter than brute force: DP over subsets or over the numbers, backtracking with pruning.
4. Approximation with a guarantee, when you need speed and can accept a bounded error.
5. Heuristics and local search when you need a good answer fast and no guarantee is required. Measure them against an exact answer on small cases.
6. Use a solver (SAT, integer programming, constraint solver) for real production problems instead of writing your own.

Let us run each one.

1. Subset sum: brute force, backtracking, and pseudo-polynomial DP

Three solvers for the same question. The brute force tries all 2^n subsets. The backtracking sorts the numbers (largest first), and stops a branch when the target is passed or the numbers that remain cannot reach it. The DP keeps a table dp[s]: can some subset make sum s?

function subsetBrute(nums, target) { const n = nums.length; for (let m = 0; m < 2 ** n; m++) { let s = 0; for (let i = 0; i < n; i++) if (m >> i & 1) s += nums[i]; if (s === target) return m; } return -1; }function subsetBT(nums, target) { const sorted = [...nums].sort((a, b) => b - a); let calls = 0; const suffix = sorted.map((_, i) => sorted.slice(i).reduce((a, b) => a + b, 0));  function go(i, rem) { calls++; if (rem === 0) return true; if (i === sorted.length || rem < 0 || suffix[i] < rem) return false; return go(i + 1, rem - sorted[i]) || go(i + 1, rem); }  return { found: go(0, target), calls }; }function subsetDP(nums, target) { const dp = new Uint8Array(target + 1); dp[0] = 1; for (const x of nums) for (let s = target; s >= x; s--) if (dp[s - x]) dp[s] = 1; return !!dp[target]; }

First, correctness. On 2,000 random small cases (up to 10 numbers each from 1 to 20) all three agreed:

random disagreements out of 2000: 0

Now speed. To get the worst case, I made all numbers even and the target odd, so the answer is "no" and every method has to look everywhere:

n=16 brute 3.9 ms | DP 0.08 ms | backtrack 0.2 ms (19739 calls)n=20 brute 68.1 ms | DP 0.06 ms | backtrack 1.3 ms (118589 calls)n=22 brute 294.7 ms | DP 0.05 ms | backtrack 4.4 ms (370307 calls)n=24 brute 1222.6 ms | DP 0.05 ms | backtrack 14.7 ms (1271307 calls)

The brute force grows about four times for every two extra items, the signature of 2^n. The backtracking calls also grow by roughly 2.5 to 3.5 times for every 2 items: pruning helps by a big constant, but it is still exponential. The DP looks flat here because the targets are small (a few hundred). Now the same DP with 200 numbers and a large target:

n=200, target 52746 DP: true 26.5 ms; 2^200 = 1.61e+60

The DP does about n x target steps, so it handles 200 numbers easily where brute force would never finish. But there is a catch, and it is the most important point in this lesson: the DP is polynomial in the value of the target, not in the length of the input. Writing the number 100,000,000 takes only 9 digits. The table has 100 million entries:

const hugeT = 1e8; subsetDP([1e8 - 1, 1, 5e7, 3], hugeT);

n=4 but target 1e8: DP time 513 ms, memory 100 MB of flags

Four numbers, and half a second plus 100 MB. If the target had 30 digits instead of 9, the table would be impossible. That is what pseudo-polynomial means. It is also not a contradiction: subset sum is NP-complete, and this DP is fast only when the numbers are small. For an interview: "small target, use the DP; huge numbers and many items, use meet-in-the-middle or a solver" (meet-in-the-middle splits the list into halves and gets about 2^(n/2); I did not run it here).

2. Knapsack: DP is exact, greedy is not

0/1 knapsack: each item has a weight and a value, take each item at most once, stay within the capacity. The greedy idea is "take the best value per weight first". The DP stores the best value for each capacity.

const knDP = (items, cap) => { const dp = new Array(cap + 1).fill(0); for (const { w, v } of items) for (let c = cap; c >= w; c--) dp[c] = Math.max(dp[c], dp[c - w] + v); return dp[cap]; };const knGreedy = (items, cap) => { let w = 0, v = 0; for (const it of [...items].sort((a, b) => b.v / b.w - a.v / a.w)) if (w + it.w <= cap) { w += it.w; v += it.v; } return v; };const knGreedy2 = (items, cap) => Math.max(knGreedy(items, cap), Math.max(0, ...items.filter((i) => i.w <= cap).map((i) => i.v)));const bad = [{ w: 1, v: 2 }, { w: 10, v: 10 }];

The tiny trap: capacity 10, an item of weight 1 and value 2 (ratio 2), and an item of weight 10 and value 10 (ratio 1). Greedy takes the first item, and then the second no longer fits.

classic greedy trap: cap 10 -> greedy 2 best 10 greedy+best single 10

knGreedy2 is the standard small fix: also compare with the best single item, and take the larger. I tested everything on 3,000 random knapsacks (3 to 10 items) against brute force:

random knapsacks 3000: DP wrong 0; greedy not optimal in 620; worst greedy ratio 0.21; with best-single fix worst 0.63

The DP matched brute force every time. Plain greedy was not optimal in 620 of the 3,000 cases, and at its worst it got only 21% of the best value. With the best-single fix the worst case I saw was 63% (the theory I remember says at least 50%, which I did not re-check). At 22 items:

n=22: brute 552 (799 ms), DP 552 (0.13 ms), greedy 552 (0.060 ms)

Here greedy happened to find the best answer. That is the danger of testing a heuristic on one input: it looks perfect until it does not. Always test on many random cases and on adversarial cases.

3. Vertex cover: a 2-approximation

Pick any edge whose two ends are both uncovered, take both ends, repeat. The edges you picked do not share nodes, and any cover must contain at least one end of each such edge, so the optimum is at least as large as the number of picked edges. You took twice that many, so you are within a factor of 2 of the best.

const vcApprox = (edges) => { const cov = new Set(); for (const [u, v] of edges) if (!cov.has(u) && !cov.has(v)) { cov.add(u); cov.add(v); } return cov; };

I checked it against the brute force on 500 random graphs of 4 to 14 nodes. It always returned a valid cover, and the worst ratio was exactly 2:

vertex cover 500 graphs: 2-approx always a cover: true; worst ratio 2.00 (limit 2); max-degree greedy worst 1.50star graph optimum 1 2-approx picks 2single edge optimum 1, approx 2

A single edge shows that the factor 2 is real: the optimum is one node, the approximation takes both. The "max-degree greedy" in the output (repeatedly take the node with the most remaining edges) did better on my small graphs, 1.5 at worst. But it has no constant guarantee in general, and the 2-approximation does. Which one is better depends on whether you value the proof or the typical result.

4. Travelling salesman: brute force, Held-Karp DP, nearest neighbour, 2-opt

Brute force tries every order of the cities. The number of orders is (n-1)!. The Held-Karp DP is smarter: dp[set][last] is the shortest path that starts at city 0, visits exactly the cities in set, and ends at last. It has 2^n x n states and each tries n moves: O(n^2 x 2^n), still exponential, but much less than n!.

function tspDP(P) { const n = P.length, N = 1 << n, D = P.map((a) => P.map((b) => dist(a, b))); const dp = Array.from({ length: N }, () => new Float64Array(n).fill(Infinity)); dp[1][0] = 0;  for (let m = 1; m < N; m += 2) for (let last = 0; last < n; last++) { const cur = dp[m][last]; if (cur === Infinity) continue; for (let nx = 1; nx < n; nx++) if (!(m >> nx & 1)) { const nm = m | 1 << nx, v = cur + D[last][nx]; if (v < dp[nm][nx]) dp[nm][nx] = v; } }  let best = Infinity; for (let l = 1; l < n; l++) best = Math.min(best, dp[N - 1][l] + D[l][0]); return best; }function tspNN(P) { const n = P.length, seen = new Set([0]), order = [0]; while (order.length < n) { const l = order.at(-1); let b = -1, bd = Infinity; for (let i = 0; i < n; i++) if (!seen.has(i) && dist(P[l], P[i]) < bd) { bd = dist(P[l], P[i]); b = i; } seen.add(b); order.push(b); } return tourLen(P, order); }

tspNN is nearest neighbour: always walk to the closest unvisited city. The 2-opt step starts from a tour and keeps reversing a part of it whenever that makes the tour shorter, until nothing improves. (Helpers dist, tourLen, tspBrute and twoOpt are in my script. 2-opt started from the plain order 0, 1, 2, ... of random points.) Random points on a 100 x 100 square:

n=8: brute 159.6 (5040 tours, 21 ms) | DP 159.6 (0.7 ms) | nearest-neighbour 184.0 (+15%) | 2-opt 159.6 (+0%)n=9: brute 290.7 (40320 tours, 49 ms) | DP 290.7 (2.1 ms) | nearest-neighbour 297.2 (+2%) | 2-opt 290.7 (+0%)n=10: brute 226.3 (362880 tours, 268 ms) | DP 226.3 (0.9 ms) | nearest-neighbour 236.8 (+5%) | 2-opt 226.3 (+0%)n=11: brute 283.7 (3628800 tours, 2959 ms) | DP 283.7 (6.3 ms) | nearest-neighbour 310.9 (+10%) | 2-opt 283.7 (+0%)

Brute force and DP agree on the best length. Brute force went from 21 ms to 2.9 seconds in three steps of n. The DP keeps going a bit further, then it hits its own wall:

n=14: DP 298.8 in 30 ms; (n-1)!/2 = 3.11e+9 toursn=16: DP 326.5 in 115 ms; (n-1)!/2 = 6.54e+11 toursn=18: DP 401.3 in 683 ms; (n-1)!/2 = 1.78e+14 tours

The DP time grows about four to six times for every two extra cities here (30, 115, 683 ms), while the tour count grows by a factor of 200 to 300. Past 25 or 30 cities even the DP runs out of time and memory. With 200 cities the heuristics are the only option:

n=200: NN 1312 NN+2opt 1168 (2-opt run 3641 ms)

(The label "NN+2opt" in my script's output is misleading: the 2-opt run started from the plain city order, not from the nearest-neighbour tour. It reduced the length from 1312 for nearest neighbour to 1168. I do not know how far either is from the optimum at n = 200, because I cannot compute that here.) For TSP where the distances obey the triangle inequality, Christofides' algorithm has a proven 1.5 factor (from memory, not run). Without the triangle inequality, no constant factor is possible unless P = NP (also from memory).

5. Graph colouring: greedy depends on the order

Greedy colouring: visit the nodes in some order and give each the smallest colour that no neighbour has. The order changes the result, and a bad order can be terrible. A "crown" graph (two groups of 5 nodes, each node joined to all nodes of the other group except its partner) can be coloured with 2 colours. In a bad order, greedy needs 5:

crown graph (bipartite, so 2-colourable): chromatic 2 greedy bad order 5 greedy good order 2random graphs where plain greedy used more colours than needed: 104 of 300

An exact search (backtracking, trying each colour for each node, nodes with the most neighbours first) finds the true minimum, but its time jumps:

n=30 random graph: chromatic 3, greedy 5, exact search 0.1 msn=50 random graph: chromatic 4, greedy 6, exact search 1.6 msn=70 random graph: chromatic 5, greedy 7, exact search 1540.8 ms

From 1.6 ms to 1.5 s when n goes from 50 to 70. The time does not grow smoothly: on one graph it is fast and on the next it explodes. That is typical for backtracking on NP-hard problems, and it is why you test on many inputs of the target size, not only on a single one.

6. SAT: backtracking with unit propagation

A SAT formula in CNF (conjunctive normal form) is a list of clauses; each clause is an "or" of literals; the formula needs all clauses true. I write literals as signed numbers, so [1, -2] means x1 or not x2. A tiny solver picks a literal, simplifies, and backtracks; a clause with a single literal is forced ("unit propagation"). This is a very small version of what real SAT solvers do (DPLL).

const satBrute = (nv, cl) => { for (let mm = 0; mm < 2 ** nv; mm++) if (cl.every((c) => c.some((l) => ((mm >> (Math.abs(l) - 1)) & 1) === (l > 0 ? 1 : 0)))) return mm; return -1; };function dpll(nv, cl) { let calls = 0; const go = (cs) => { calls++; if (cs.length === 0) return true; if (cs.some((c) => c.length === 0)) return false;    const unit = cs.find((c) => c.length === 1); const l = unit ? unit[0] : cs[0][0];    for (const lit of unit ? [l] : [l, -l]) { const next = cs.filter((c) => !c.includes(lit)).map((c) => c.filter((x) => x !== -lit)); if (go(next)) return true; } return false; };  return { sat: go(cl), calls }; }

On 500 random 3-SAT formulas (3 to 10 variables) the two solvers never disagreed. Then two larger formulas with about 4.3 clauses per variable, a ratio that is known (from my memory, unverified) to be hard for random 3-SAT:

brute vs backtracking disagreements on 500 random 3-SAT formulas: 0vars=18 clauses=77: brute sat=true 13.9 ms | backtracking sat=true 0.40 ms (32 calls)vars=22 clauses=95: brute sat=false 1248.6 ms | backtracking sat=false 1.07 ms (163 calls)

When a formula has no solution, brute force must try all 2^n settings (1.2 seconds at 22 variables); when it has one, brute force can stop early. Backtracking stayed tiny on both. That does not prove it is polynomial: real instances can be built that make it explode. It shows why modern SAT solvers are used in practice on huge inputs even though the problem is NP-complete: worst-case hardness is not the same as typical-case hardness.

Which approach when

Common mistakes

1. Saying "it is NP-hard" and stopping. Always continue: size, exact method, approximation, heuristic.
2. Claiming "NP means not polynomial". NP means checkable in polynomial time.
3. Reducing in the wrong direction when proving hardness.
4. Calling subset sum polynomial because of the DP. The DP is pseudo-polynomial.
5. Trusting a greedy rule without a counter-example search. Test against brute force on small random cases.
6. Mixing up the optimisation problem and the decision problem. TSP "find the shortest tour" is NP-hard; "is there a tour under L" is NP-complete.
7. Spending the interview looking for a fast exact solution to a problem that is a known NP-complete one.

Interview questions

Key takeaways

• P means quick to solve. NP means quick to check. NP-complete means the hardest in NP. Whether P equals NP is open.
• NP-hard problems often look like "best subset, ordering or assignment" with 2^n or n! options. Small input limits hint at an exponential intended solution.
• "It is NP-hard" starts the answer. Continue with input size, exact search for small n, a pseudo-polynomial DP when numbers are small, an approximation with a guarantee, or a heuristic you test.
• Subset sum and knapsack DPs are fast only for small numbers (pseudo-polynomial).
• Greedy is not safe for 0/1 knapsack, graph colouring or TSP. Compare it with brute force on small random inputs.
• The 2-approximation for vertex cover is simple, with a proof: pick edges that share no node and take both ends.
• Worst-case hardness is not typical-case hardness: SAT solvers do well on real inputs.

What's next

Lesson 7: String Searching: Naive, KMP, Rabin-Karp and Z. This is the opposite case: a problem that looks like it needs a lot of comparisons but has several fast exact algorithms. Practise first: take the subset sum DP above and change it to return the actual subset, not only yes or no, then check it against brute force on random inputs.