P vs NP: when a thousand cores won't help

There are two moments when P versus NP matters to a working programmer. The first is a slow system and someone says, “just throw more cores at it.” The second is a job interview where the interviewer asks whether you can beat an exponential solution. This article covers both: what P and NP mean, why a thousand cores cannot rescue an exponential algorithm, and what to say and do in each situation. You do not need a proof. You need a definition, a number, and one honest sentence for a room full of people pretending to know what NP means.

P versus NP is one of the Clay Mathematics Institute’s Millennium Prize Problems, one of seven questions in mathematics with a one-million-dollar prize each. That is not a metaphor. Nobody has collected it. You are not here to solve the problem. You are here to understand the question and why it matters to systems and interviews.

Polynomial time: what “fast” actually means

The site’s What O(n) actually promises article explains the notation: a complexity like $O(n^2)$ says the work grows with the size of the input, and that growth determines whether a program scales. Polynomial time is the family of those “nice” shapes: anything whose Big O expression is a polynomial, $O(n)$, $O(n^2)$, $O(n^{10})$, with the input size $n$ raised to a fixed power. The algorithms textbook states the split plainly:

Many algorithms can be solved in polynomial time where the Big-Oh expression can be written as a polynomial. These are considered tractable problems. There is also the set of problems that cannot be solved in polynomial time. These are considered intractable.

The word “tractable” matters. A tractable problem scales: double the input, and the runtime multiplies by a constant—four for $O(n^2)$, eight for $O(n^3)$. You can plan around that. An intractable problem belongs to the other family: the exponential family, $O(2^n)$ and $O(n!)$, where the runtime itself doubles every time you add one element. The graph-algorithms book draws the line: a polynomial-time algorithm “has a running time bounded by a polynomial function of its input, and an exponential algorithm is the one which does not”—searching a list of $n$ items takes $n$ steps, while “listing all permutations of $n$ numbers is an example of an exponential algorithm.”

Exponential is not merely “worse.” It is a cliff. $O(n^2)$ on a hundred thousand items is a hundred billion operations—large, but a machine can chew through it. $O(2^n)$ on a hundred items is more operations than there are atoms in the universe. No constant factor—no faster machine, no cleverer compiler—changes that number, and the next item doubles it again. That cliff is the subject of this article.

P and NP: finding vs. checking

Here is the part people get wrong. Read it twice. NP does not mean “not polynomial.” It means nondeterministic polynomial, a name left over from an old way of describing the class. The definition is about checking, not solving.

• P is the class of problems where you can find the answer in polynomial time.
• NP is the class of problems where you can check a proposed answer in polynomial time.

The graph-algorithms reference defines the second one formally: “The complexity class Nondeterministic Polynomial (NP) is the set of decision problems that can be verified by a polynomial algorithm.” The proposed answer is the certificate. The polynomial-time checker that accepts or rejects it is the certifier. The concrete example in the book is a set of vertices in a graph: checking that no two are connected takes two nested loops, $O(n^2)$, so the problem is in NP even though finding a large such set is hard.

Sudoku makes the distinction clear. Checking a completed grid is instant: nine rows, nine columns, nine boxes, and a few dozen comparisons. Filling the grid is hard—generalize the puzzle to $n \times n$ and the search explodes. The traveling-salesperson problem gives the same pattern: “Checking the length of a route and comparing it to other routes is polynomial, but finding the shortest route requires going through all possible combinations.” Easy to check, hard to find. That difference is the shape of the field.

Here is the famous question: is P equal to NP? If finding could always be reduced to checking—if every problem with a fast verifier also had a fast solver—the two classes would collapse into one. The consequences would be seismic: a whole family of practical problems (scheduling, routing, packing, breaking cryptography, which relies on problems that are easy to check but believed hard to find) would suddenly have fast algorithms. The reference book is careful: “The NP class includes P (P ⊂ NP)… but whether P = NP has not been determined and remains a grand challenge in Computer Science.” Most researchers believe they are different. Nobody knows. The million dollars are still on the table.

NP-complete: the hardest of the hard

Within NP sits a special tier: NP-complete problems, each at least as hard as every other problem in NP. The definition has the property that makes the class practical: “A problem which is both NP-hard and a member of NP is known as NP-complete. Because every NP-complete problem can be reduced to every other NP-complete problem, reducing any NP-complete problem to a new problem” proves the new one is NP-complete too.

“Reduced” means a translation. Convert instances of problem A into instances of problem B so that a fast solver for B gives you a fast solver for A. Because those translations chain, the NP-complete problems are, in a precise sense, the same problem wearing different costumes: the satisfiability problem (SAT) first, then traveling salesperson, subset sum, knapsack, graph coloring, partition, and hundreds more. The practical consequence is simple: you only have to recognize one. If your problem contains subset sum—“can a subset of these items sum to this total?”—as a special case, then it is NP-complete, and no one on Earth has a guaranteed polynomial-time algorithm for it. Finding one would mean finding the million-dollar proof. That recognition is the skill in the interview section: know when to stop searching for the perfect algorithm and choose a practical one.

Why concurrency cannot fix exponential

Here is the first real-world moment: a slow system and the suggestion that more cores will save it. The truth is blunt: parallelism is a constant factor, and exponential growth eats constant factors for breakfast.

Adding cores divides the work. If an algorithm takes $2^n$ steps, a machine with $p$ cores finishes in roughly $2^n / p$ time. That looks useful until you calculate the result. With twice as many cores, you handle one more element in the same wall clock. A thousand cores—$\log_2(1000) \approx 10$—buy you ten more elements, ever. Each new input element doubles the runtime, no matter how the hardware grows. Concurrency distributes work across space; the exponential cliff concerns time.

Amdahl’s law explains why parallelism runs out of room, even in the best case. The concurrency literature states its purpose plainly: “you can use Amdahl’s Law to give you an upper bound on the speedup you can attempt to achieve.” The bound is stingy: “75% parallelism can get no more than 4× speedup (on an infinite number of cores). This illustrates the fact that the speedup of a concurrent application is ultimately dependent on the portion of serial execution.” Work that cannot be parallelized—gathering results, deciding the next step—caps the payoff no matter how many cores you rent. Do not take that as “don’t parallelize.” Parallelize the right thing. Parallelizing a polynomial algorithm can produce real speedups. Parallelizing an exponential one buys a few extra elements and calls it a win.

Concurrency can help with hard problems. An exponential search is usually a search tree, like the shape from the binary trees article grown to its full exponential depth. The branches are independent, so the tree splits cleanly across workers: each worker explores a subtree, prunes hopeless branches, and reports back. On the BEAM, this is natural concurrency—spawn one process per branch, stream the work with Task.async_stream, and let workers that reach dead ends crash harmlessly under the site’s let-it-crash philosophy. The work is genuinely embarrassingly parallel. The accounting does not change: the search is still exponential. The cores provide a head start, not a cure.

The site applies one more concurrency lesson every day: the execution runners that grade your code do not know whether your solution is exponential or simply infinite. A $2^{60}$ search and a while true loop look identical from the outside—work keeps happening, answers never arrive—so the runner imposes a hard timeout and stops. A concurrent system has the same problem. You cannot distinguish “still working” from “never finishing,” so bound the wait with timeouts and budgets, not hope. The exponential algorithm is not just slow. It is undistinguishable from broken, and systems must be built accordingly.

What you do instead: the coping menu

When you recognize an NP-complete problem, do not panic. Pick from the short menu in the graph-algorithms book. Faced with an intractable problem, “we can do one of the following”:

• Attempt to solve a simpler or a restricted version of a problem which can be accomplished in polynomial time.
• Implement a polynomial-time probabilistic algorithm which provides the correct solution only with very high probability.
• Use a polynomial-time approximation algorithm with a proven approximation ratio.
• When all fails, we can use some heuristics which are commonsense rules to design polynomial-time algorithms.

Four moves. Each starts from the same fact: the guarantee is what you give up, not the problem. Restrict the inputs (fixed small size, one dimension bounded), and the hard problem becomes a polynomial one on that restricted domain. Accept randomness, and a Monte Carlo or Las Vegas algorithm gets the right answer with overwhelming probability in polynomial time. Accept approximation, and a greedy or rounding algorithm delivers an answer provably within a factor of the best one. Accept heuristics, and you get something that works on the inputs you have—tested, not proven. There is a fifth move, especially important in interviews and practice: remember that the instance you have is not the worst case. An exponential algorithm on twenty items is instant. NP-completeness concerns guarantees as the input grows without bound; a well-pruned backtracking search on a small, realistic input is often the professional solution. The search tree from the binary-trees article is what backtracking walks: visit a branch, check the constraint, and prune when the constraint dies. Pruning is not a heuristic. It is the exponential algorithm refusing to visit most of the tree.

What to say in the interview

The interview moment is simpler than it looks because interview problems are chosen to be solvable. Classic hard-looking interview problems are usually NP-complete in disguise with a small input: subset sum (partition a list into two equal halves), traveling salesperson with a handful of cities, N-Queens, graph coloring. The interviewer knows they are exponential. The question is whether you know it too and what you do with that knowledge.

Use three beats. First, name the complexity: “the naive solution is $O(2^n)$ because every subset is a candidate.” Second, name the class: “this is subset sum, which is NP-complete - it is one of the problems where every instance of every other NP problem can be hidden.” Then say the golden line once and correctly: “so a guaranteed polynomial solution for it would prove P equals NP, and nobody has that.” Third, pivot to practice: “with these constraints - the list has at most fifteen items - a pruned backtracking search is the intended solution; if the input could grow, I would look at an approximation or a restriction instead.” That is the move: recognize the problem, state the guarantee honestly, and choose the practical solution.

Two anti-patterns are worth naming because interviewers see them constantly. The first is silently hunting for the polynomial algorithm that does not exist, burning the whole session on a search that is literally a prize problem. The second is declaring “it’s NP-complete, so we can’t solve it” and stopping. NP-complete is not “impossible”; it is “no guaranteed fast algorithm.” The interview tests that difference: a hard problem and an impossible one are different, and the candidate who knows which one they hold can choose the right tool—prune, approximate, restrict, or accept the small instance.

The contrast that makes this clear is on this site. Coin Change - “given coins of distinct denominations and a total amount, return the fewest coins needed” with unlimited coins - is a dynamic-programming exercise, polynomial-ish and solvable, because the unlimited supply and bounded target give the table a shape to fill. Change one word—each coin can be used at most once—and you have subset sum, NP-complete, the same costume, a different class. That one-word difference, and knowing which side a problem falls on, is the skill this article teaches. The site’s own problems are all in P because the graders need deterministic, fast verdicts, so the exercises stay on the tractable side of the line. The interview asks whether you know where the line is and what to do on the other side.

Where to go next

• What O(n) actually promises - the notation behind polynomial and exponential, and why the shape of growth is what matters.
• Binary trees: where the log in O(log n) lives
  • the search tree that exponential algorithms grow to full depth, and the doubling argument that made the log.
• Recursion: the pattern that calls itself
  • the machinery behind backtracking search.
• Let it crash and What concurrency is
  • the BEAM model that makes splitting a search tree across a million processes natural, and the philosophy that makes it safe.
• Coin Change on /problems - the polynomial side of the one-word difference.
• Subset Sum Count - the exercise that makes the combinatorial explosion measurable: count subsets summing to a target, and feel why enumerating all $2^n$ of them stops being an option.
• Sorting: the wall at n log n - the other famous limit: no comparison sort beats $n \log n$, for information reasons a thousand cores cannot move.
• The halting problem: why code can only be run, never read
  • the undecidability family this article’s “impossible” belongs to: one step past “no fast algorithm” into “no algorithm at all”.

P versus NP asks whether finding is ever harder than checking. P contains the problems we can solve fast; NP contains the problems we can verify fast. The million-dollar question is whether they are the same set. You do not need the proof—nobody has it. You need the definition to name a problem’s class, the arithmetic to know that a thousand cores buy ten input elements and nothing more, and the menu to choose restriction, randomness, approximation, or pruning instead of a miracle. The interviewer is not asking you to solve P vs NP. They are asking whether you know what the question means. That, unlike the prize, is solvable.