What Is the P vs NP Problem? The Question Computer Science Can't Answer
- P contains problems solvable in polynomial time; NP contains problems whose solutions can be verified in polynomial time. P is a strict subset of NP.
- The P vs NP problem asks whether every easily-verified problem is also easily-solved. Almost certainly no, but no proof exists — the Clay Institute's $1M prize is unclaimed.
- NP-complete problems (SAT, subset sum, traveling salesman) are the hardest in NP. A polynomial-time solution to any one would solve all of NP simultaneously.
- Pseudo-polynomial DP solves subset sum and 0/1 knapsack in O(n × W), but only when the numeric bound is small. The general problem stays NP-complete.
- In coding interviews, recognizing NP-complete variants and explaining why no polynomial solution exists is a senior-level signal interviewers explicitly score.
- Approximation algorithms (like the 2-approximation for TSP) are the practical answer when exact solutions are intractable in the general case.
Somewhere, right now, a computer is solving a Sudoku puzzle. It tries every option, backtracks when it gets stuck, and eventually finds the one arrangement that works. That takes effort. Now imagine asking it to verify whether a completed Sudoku grid is valid. That takes about a second: scan rows, columns, and boxes. One task is hard. The other is easy. That gap is P vs NP, and it is the most important unsolved problem in computer science. Some of the smartest people on earth have spent 50 years staring at it. Nobody has collected the $1 million prize. You are not going to solve it this afternoon.
Two Kinds of Hard
Some problems are hard because computing the answer takes a long time. Others are hard because finding the answer takes a long time, even though checking it is fast. That distinction is the entire premise.
Computer scientists split these into two categories: problems that are hard to solve, and problems that are hard to solve but easy to verify.
The verification gap is what makes one category mathematically interesting, and practically consequential. If checking is always faster than finding, life continues as normal. If they turn out to be the same, well. We will get to that.
P: The "Easy" Problems (Theoretically Speaking)
P stands for polynomial time. A problem is in P if there exists an algorithm that solves it in O(n^k) time for some constant k.
Polynomial time means the runtime grows as a polynomial function of the input size. O(n), O(n log n), O(n²), O(n³) all qualify. O(2^n) and O(n!) do not.
Some problems firmly in P:
- Sorting an array: O(n log n)
- Shortest path in a weighted graph (Dijkstra): O((V + E) log V)
- Binary search: O(log n)
- Matrix multiplication: roughly O(n^2.37) via Strassen's algorithm
These are "easy" in the theoretical sense. Not trivial to implement. Theoretically easy is different from easy-easy. Ask anyone who has debugged an off-by-one error in Dijkstra at 2am. But their runtimes stay manageable as input grows. For background on how we measure this, see what time complexity actually means.
The choice of polynomial as the dividing line goes back to 1965, when Cobham and Edmonds independently proposed it as the right measure of tractability. The bar is not arbitrary. Polynomial algorithms compose: if step A runs in O(n²) and step B runs in O(n³), the whole thing is still polynomial. Exponential algorithms do not have that property.
NP: Not "Not Polynomial" (Everyone Gets This Wrong)
Here is where most explanations go wrong. NP does not stand for "not polynomial." It stands for nondeterministic polynomial time.
The name is historical, confusing, and responsible for a million wrong flashcards. What it actually means: a problem is in NP if a proposed solution can be verified in polynomial time.
NP is defined by how fast you can check an answer, not how fast you can find one. Write that on your hand before an interview.
The "nondeterministic" part comes from a theoretical model: a nondeterministic Turing machine that can magically guess the right answer, then verify it in polynomial time. This is a mathematical abstraction, not a real machine. Nobody is building one. It just gives a precise definition for the class.
Every problem in P is also in NP. If you can solve something quickly, you can definitely verify it quickly. P is a strict subset of NP. The open question is whether the reverse holds: is every problem that is easy to verify also easy to solve?
Some problems in NP with no known polynomial-time solution:
- Does this boolean formula have an assignment of true/false values that makes it evaluate to true?
- Can a salesman visit N cities exactly once with total distance under K?
- Is there a subset of these integers that sums to exactly the target?
You can check any proposed answer to these in polynomial time. Finding that answer from scratch is a completely different story.
A Concrete Example: Subset Sum
The problem: given a set of integers and a target value, does any subset sum to exactly that target?
# Does any subset of this list sum to 14? numbers = [3, 7, 1, 8, 5, 2] target = 14 # Proposed answer: [7, 5, 2] # Verification: 7 + 5 + 2 = 14. Three additions. Done.
Checking that [7, 5, 2] sums to 14 takes three additions. Polynomial. Trivial.
Finding whether any such subset exists? With n numbers, you have 2^n possible subsets. For n = 20, that is about one million subsets. For n = 100, the count exceeds the estimated number of atoms in the observable universe. Brute force runs in O(2^n). No known polynomial-time algorithm exists.
There is a dynamic programming approach that runs in O(n × target), which is useful when the target value is small. But "small target" is a constraint you imposed, not a property of the general problem. As the input grows without bound, the DP solution's cost can still grow exponentially. The runtime is polynomial in the numeric values but exponential in the number of bits needed to represent them. It is a useful trick with a precise limit. See how dynamic programming works for the full breakdown.
NP-Complete: The Hardest of the Hard
Inside NP, there is a special class: NP-complete.
A problem is NP-complete if:
- It is in NP (solutions can be verified quickly), and
- Every other problem in NP can be reduced to it in polynomial time
That second condition is the critical one. It means NP-complete problems are at least as hard as everything else in NP. If you find a polynomial-time solution to any single NP-complete problem, you have automatically solved every problem in NP, which would prove P = NP.
The first NP-complete problem was identified by Stephen Cook in 1971: Boolean Satisfiability, or SAT. The Cook-Levin theorem showed that SAT is in NP and that every NP problem reduces to it. Since then, thousands of problems have been proven NP-complete by reduction: show that SAT (or any other known NP-complete problem) can be translated into your problem in polynomial time, and you inherit the hardness.
The most common NP-complete problems you will encounter:
| Problem | What you're given | What you're asking |
|---|---|---|
| SAT | Boolean formula | Does any assignment of true/false satisfy it? |
| Subset Sum | Set of integers, target | Does any subset sum to the target? |
| 0/1 Knapsack | Items with weights and values | Can you reach value V within weight limit W? |
| Traveling Salesman (decision) | Cities and distances | Is there a tour under length K? |
| Graph Coloring | Graph, k colors | Can you color it so no adjacent nodes share a color? |
All share the same feature: a proposed solution is checkable quickly, but no one knows how to find it quickly. Backtracking is the standard brute-force approach, systematically exploring the solution space and pruning branches that cannot work.
The optimal solution for TSP was available the whole time
Why the P vs NP Problem Is Worth $1 Million
In 2000, the Clay Mathematics Institute listed seven unsolved problems and offered $1 million for a solution to each. P vs NP made the list. As of 2026, it remains unsolved.
A million dollars. Sitting there. Unclaimed for over two decades. At some point you start to suspect nobody's getting that check.
The overwhelming consensus among researchers is that P does not equal NP. A widely cited 2012 survey found that over 80% of theoretical computer scientists believe this, with the number rising each year. But consensus and proof are very different things.
What happens if P = NP:
- RSA, AES, and public-key cryptography break. Private keys become computable. Internet banking, secure communications, and blockchain systems all fail.
- Drug discovery and protein folding become tractable, potentially transforming medicine.
- Scheduling, logistics, and resource allocation problems that currently require approximations would be solvable exactly.
If P does not equal NP (the expected answer), some problems are inherently hard for any computer, not just current ones. The encryption securing the internet rests on a provably solid foundation.
One nuance worth knowing: even if P = NP were proven true, the polynomial-time algorithm might have an astronomical exponent, something like O(n^100). Technically correct. Completely impractical. You solve every NP problem in theory, then watch your server burst into flames trying to factor a 512-bit key.
The worst case for many NP problems is more accurately the expected case
What This Means for Coding Interviews
You will not be asked to solve NP-complete problems in an interview. You will be expected to recognize them and say so.
The key skill is identifying when a problem is NP-complete and pivoting to the right strategy, rather than spending 35 minutes searching for an optimal polynomial-time solution that does not exist.
Recognize the instance. Subset sum, 0/1 knapsack, graph coloring, and traveling salesman are NP-complete in the general case. When you see one, say so. "This is a variant of the subset sum problem, which is NP-complete in the general case" is a strong signal that you understand complexity classes. It also tells the interviewer you're not about to waste both of your time.
Use DP as a pseudo-polynomial workaround. Both subset sum and 0/1 knapsack have dynamic programming solutions that run in O(n × target) or O(n × W). These work when the target or weight bound is small. The runtime is polynomial in the numeric values, but exponential in the number of bits needed to represent them, which is why they do not contradict NP-hardness. The constraint that makes DP practical is often given to you in the problem statement. Notice it.
Know when to approximate. Traveling salesman has no known polynomial solution for the general case, but a 2-approximation (a tour guaranteed within 2x optimal) exists. Interviewers at senior levels may ask about approximation strategies, not exact solutions. Knowing that a greedy nearest-neighbor heuristic exists is a useful thing to say.
Communicate the tradeoff explicitly. Something like: "The general knapsack problem is NP-hard, but we can solve it efficiently in O(n × W) with DP, which works here because the capacity is bounded." That single sentence tells an interviewer you understand complexity classes, not just syntax.
SpaceComplexity runs voice-based mock interviews scored on exactly this dimension. For NP-complete adjacent problems, being able to articulate the class matters as much as writing the code.
Key Takeaways
- P is problems solvable in polynomial time. NP is problems where solutions can be verified in polynomial time. P is a subset of NP.
- P vs NP asks: is every quickly-verifiable problem also quickly-solvable? Almost certainly not, but nobody has proved it. The $1 million Clay prize is unclaimed.
- NP-complete problems are the hardest in NP. A polynomial-time solution to any one would prove P = NP and solve all of NP.
- In interviews: recognize NP-complete variants, reach for DP when the problem has bounded parameters, use approximation when asked about general cases, and explain the tradeoff out loud.