What is the P vs NP problem, and which class do crypto problems like factoring belong to?
P = problems solvable in polynomial time. NP = problems whose solutions can be verified in polynomial time, but not (known) solved that way. The famous open question is whether P = NP.
Two graph problems that look similar but have wildly different complexities:
| Problem | Question | Class |
|---|---|---|
| Eulerian circuit | Visit every edge exactly once | In P — efficient algorithm known |
| Hamiltonian circuit | Visit every vertex exactly once | NP-complete — no known efficient algorithm |
If someone hands you a Hamiltonian path you can verify it in O(n) — just walk the path and check each vertex appears once. But finding one in an arbitrary graph appears to require trying exponentially many possibilities.
Why this matters for crypto:
- Factoring (RSA's foundation) is in NP but is not known to be NP-complete. It's in the "NP-intermediate" class — possibly easier than NP-complete problems, possibly polynomial we just haven't found yet.
- If P = NP, every NP problem (including factoring) becomes polynomial → public-key cryptography is broken.
- The Clay Millennium Prize offers $1 million for a proof either way — open since 2000.
The honest answer: modern crypto rests on the conjecture that factoring / discrete log are hard. They've resisted decades of attack, so we trust them — but they aren't proven hard.
Tip: Most researchers believe P ≠ NP, but the proof is famously elusive. Practical crypto people just deploy and watch for breakthroughs.