Suppose you have a 1000-piece jigsaw puzzle. You are given a completed puzzle. Can you tell if it’s correct? Yes, obviously, you can see and check if all the pieces fit together. But what if you had to solve the puzzle from scratch? That would take way longer, right?
Does P = NP? In other words, if a solution to a problem can be verified quickly (in polynomial time), can it also be found quickly?
This is arguably the most important open question in computer science and one of the seven Millennium Prize Problems with a $1 million reward from the Clay Mathematics Institute. It’s been unsolved since Stephen Cook formalized it in 1971. Solve it, and you’ll be famous forever.
What are P and NP anyway?
P (Polynomial Time)
P is the class of problems that can be solved efficiently — meaning in polynomial time. Polynomial time means the time grows like nk for some constant k (like n2, n3, n10, etc.) as the input size n grows.
Examples of problems in P:
- Sorting: Given n numbers, arrange them in order. O(n log n).
- Finding shortest paths: Dijkstra’s algorithm. O(n² or better).
- Checking if a number is even: O(1). Trivial!
- Multiplying two numbers: O(n²) with standard multiplication.
These are “easy” problems in the computational sense. Even if n is large, polynomial time algorithms are practical.
NP (Nondeterministic Polynomial Time)
NP is the class of problems where a solution can be verified efficiently — in polynomial time — even if we don’t know how to find it efficiently.
Examples of problems in NP:
- Sudoku: Given a completed grid, checking if it’s valid is easy (polynomial). Finding the solution is much harder.
- Traveling Salesman Problem: Given a route, checking its length is easy but finding the shortest route is exponentially harder.
- Boolean Satisfiability (SAT): Checking if a given variable assignment satisfies a formula is easy but finding such as assignement is hard.
- Factoring: Finding factors of a number is hard — else RSA wouldn’t work.
P ⊆ NP. Everything in P is also in NP because if you can solve a problem quickly, you can certainly verify a solution quickly (just solve it and check if your answer matches).
But is NP ⊆ P? That’s the million-dollar question.
Does P = NP?
Two possibilities:
1: P ≠ NP (Most people believe this)
This would mean there’s a fundamental difference between finding and checking solutions. Some problems are inherently harder to solve than to verify.
Implications:
- There are problems that are easy to check but fundamentally hard to solve
- One-way functions exist (easy to compute, hard to invert)
- Cryptography is safe (factoring is hard, encryption works)
- Many optimization problems will never have efficient algorithms
- The universe has computational boundaries
This is what 99% of computer scientists believe. It just feels right. If P = NP were true, it would be shockingly counterintuitive.
2: P = NP (The world-changing scenario)
This would mean that for every problem where you can check solutions quickly, you can also find solutions quickly — we just haven’t discovered the algorithms yet.
Implications:
- Every NP problem becomes tractable
- Modern cryptography collapses (RSA, elliptic curve, etc.)
- Massive breakthroughs in optimization, scheduling, drug discovery
- Proving mathematical theorems becomes automated
- Possibly the end of creativity as we know it? (if finding solutions is as easy as checking them)
This would be the most important discovery in computer science history. It would revolutionize everything. But it seems too good (or bad?) to be true.
NP-Complete
Some problems in NP are special — they’re the hardest problems in NP. These are called NP-Complete.
A problem is NP-Complete if:
- It’s in NP (solutions can be verified quickly)
- Every other problem in NP can be reduced to it in polynomial time
In other words, if you could solve any NP-Complete problem efficiently, you could solve all NP problems efficiently. They’re all equally hard.
Famous NP-Complete problems:
- SAT (Boolean Satisfiability) — the first proven NP-Complete problem
- Traveling Salesman Problem
- Graph Coloring
- Knapsack Problem
- Hamiltonian Path
- Clique Problem
- Vertex Cover
If you find a polynomial-time algorithm for any NP-Complete problem, you’ve proven P = NP. All these problems would suddenly become easy.
Conversely, if you prove even one NP-Complete problem cannot be solved in polynomial time, you’ve proven P ≠ NP.
NP-Hard
NP-Hard problems are at least as hard as NP-Complete problems, but they might not even be in NP (solutions might not be verifiable quickly).
- Halting Problem — undecidable, not even in NP
- Optimizing the Traveling Salesman (finding the shortest tour, not just checking if a tour exists under a length)
- Chess and Go (finding optimal moves)
These are the nightmare problems. Some aren’t even solvable by any algorithm (like the halting problem).
The complexity hierarchy
- P: Efficiently solvable
- NP: Efficiently verifiable
- NP-Complete: Hardest problems in NP
- NP-Hard: At least as hard as NP-Complete
- PSPACE: Solvable with polynomial space
- EXP: Solvable in exponential time
- Decidable: Solvable by some algorithm (even if it takes forever)
We know: P ⊆ NP ⊆ PSPACE ⊆ EXP
We don’t know where the strict inequalities are. Maybe P = NP = PSPACE? (Unlikely but not disproven)
Why is this so hard to prove?
The proving P ≠ NP direction
To prove P ≠ NP, you’d need to show that no possible algorithm can solve an NP-Complete problem in polynomial time.
This requires proving a lower bound: demonstrating that any algorithm for, say, SAT must take at least exponential time in the worst case. For most problems, we have no idea how to prove they require a certain amount of time.
The proving P = NP direction
To prove P = NP, you’d need to find a polynomial-time algorithm for an NP-Complete problem. Just one.
Sounds easy but thousands of brilliant minds have tried for 50+ years. If such an algorithm existed — someone probably would have found it by now. The fact that nobody has is strong (but not conclusive) evidence that P ≠ NP.
There’s also a catch, even if P = NP, the polynomial might be something ridiculous like n1000, which is technically polynomial but utterly useless in practice.
Why this matters
Cryptography
Modern encryption (RSA, elliptic curve) relies on the assumption that certain problems are hard to solve but easy to verify. Specifically —
- Factoring large numbers is hard
- Discrete logarithm is hard
If P = NP, these problems become easy, and all current cryptography breaks. Online banking, secure messaging, e-commerce — all become vulnerable.
Optimization
Countless industries rely on solving NP-Hard optimization problems approximately:
- Supply chain logistics (TSP variants)
- Scheduling (job shop scheduling)
- Resource allocation (knapsack variants)
- Network design (Steiner tree, minimum cut)
If P = NP, we could solve these optimally in polynomial time. This would save billions of dollars and revolutionize industries.
Mathematics and proofs
Checking if a proof is valid is easy (just read it and verify each step). Finding proofs is hard.
If P = NP, we could automate theorem proving at an unprecedented scale. Mathematics could be revolutionized — or rendered obsolete, depending on your perspective.
Drug discovery and protein folding
Many problems in biology reduce to NP-Complete problems —
- Protein folding (finding lowest energy configuration)
- Drug molecule design
P = NP would accelerate medical breakthroughs exponentially.
Artificial Intelligence
Many AI tasks involve searching huge spaces for optimal solutions. If P = NP, AI would become vastly more powerful, possibly approaching general intelligence.
Or maybe not. Intelligence might require more than efficient search.