🤔 okay so what's the question?
I kept hearing P vs NP at conferences and nodding along like I understood it. I did not understand it. so I decided to actually sit down and figure it out.
turns out the question is deceptively simple:
is finding an answer always harder than checking one?
like… if you can quickly verify a solution is correct, does that mean you can also quickly find a solution?
that's it!! that's the whole question!! it just took me a while to realize that's what people meant.
🧩 let's talk about sudoku
this is the example that finally made it click for me.
→
solved! can you verify? ✅
KEY INSIGHT
checking if a completed sudoku is valid?
easy. scan the rows and columns. done in seconds.
filling in a blank sudoku from scratch? that's
genuinely harder work.
P vs NP is asking: is this difference real? or is there always some clever trick that makes solving just as fast as checking?
📚 okay but what do P and NP actually mean
poly-
nomial
time!!
"quickly" in computer science has a specific meaning. it means the time to solve a problem doesn't explode as the problem gets bigger. the technical term is polynomial time — which is where the P comes from.
P
can be solved quickly
(polynomial time)
⊆?
NP
can be verified quickly
(polynomial time)
WAIT
NP does
not stand for "not polynomial"!! I thought this for an embarrassingly long time.
it stands for
"nondeterministic polynomial" — which is a confusing name but basically means "you can verify a solution fast."
every problem in P is also in NP (if you can solve it fast, you can also verify it fast — just solve it and check!). the question is whether NP is bigger than P, or exactly the same.
💥 why would anyone care about this
okay so here's where it gets wild. if someone proved P = NP, it would break basically everything:
🔓
encryption is dead. RSA, the thing keeping your bank account safe, relies on factoring big numbers being hard. P=NP means it's easy.
🤯
HTTPS means nothing. all the little padlocks in your browser? gone. the math underneath them collapses.
💊
drug discovery becomes fast. protein folding and drug design are NP problems. they'd suddenly be solvable.
🗺️
logistics gets solved. the "travelling salesman" problem (optimize a delivery route across 1000 cities) — done instantly.
THE STAKES
basically:
most of modern cryptography is a bet that P ≠ NP. we don't know if that bet is correct. we've just been hoping really hard for 50 years.
⭐ the really interesting bit: NP-complete
here's a thing I didn't know: there's a special category of problems called NP-complete.
an NP-complete problem is one where:
1. it's in NP (you can verify solutions fast)
2. if you could solve it fast, you could solve ALL NP problems fast
so these are like the "hardest" problems in NP. they're all secretly connected to each other. if you cracked one, you cracked them all.
- sudoku (generalized) → NP-complete
- travelling salesman (decision version) → NP-complete
- satisfiability (SAT) → NP-complete (and the first one ever proved to be!)
- tetris (whether you can survive a given sequence of pieces) → also NP-complete!! wild right??
so when people say "prove P=NP" they really mean "solve any NP-complete problem efficiently." they're all equivalent.
📅 a very quick history
1971
Stephen Cook formally defines the problem. proves SAT is NP-complete. the race begins.
1972
Richard Karp shows 21 more problems are all NP-complete. suddenly everyone is very nervous.
2000
Clay Mathematics Institute adds P vs NP to their Millennium Prize Problems. prize: $1,000,000.
2010
Vinay Deolalikar claims to prove P ≠ NP. the internet gets very excited for about two weeks. then experts find errors. 😔
now
still unsolved. ~99% of computer scientists believe P ≠ NP. nobody can prove it.
🗳️ what do people actually think?
in a 2019 poll of complexity theorists:
POLL RESULTS
~88% believe P ≠ NP
~9% are unsure
~3% believe P = NP (bold!!)
the reason most people believe P ≠ NP is basically vibes + evidence. we've tried really hard to find fast algorithms for NP-complete problems for 50 years and found nothing. that's a strong signal!
but "we haven't found it" is not a proof. and in math, a proof is the only thing that counts.
✅ okay so to summarize
- P = problems you can solve quickly
- NP = problems you can verify quickly
- P vs NP = are these the same set of problems?
- NP-complete = the hardest problems in NP — solve one, solve all
- if P = NP: encryption breaks, but science gets superpowers
- if P ≠ NP: some problems are genuinely hard and there's a real wall between "finding" and "checking"
- after 50+ years: nobody knows. the million dollar prize is unclaimed.
THE THING THAT BLOWS MY MIND
the question is so
clean. is finding harder than checking? and we genuinely, truly, completely do not know the answer. that's kind of beautiful??
~ ~ ~ ~ ~ ~ ~ ~ ~