P vs NP explained: why a $1M unsolved problem underpins all of modern cryptography
sudoraohacker · x · 2026-11-23
A accessible long thread explaining P vs NP:
- P is the set of problems computers can solve quickly (sorting, shortest paths, multiplication); NP is the set where answers can be verified quickly even if finding them is hard (like a filled-in Sudoku).
- What P = NP means: if an answer is fast to check, is it also fast to find? Almost everyone believes the answer is no, but it remains unproven — one of the $1M Millennium Prize problems.
- Why it matters: modern security (HTTPS, online banking, passwords) rests on the assumption that some problems are brutally hard to solve but easy to verify, with factoring large numbers as the classic case. If P = NP, that wall could fall very fast. The accompanying diagram contrasts the P≠NP world most researchers believe in with the P=NP world where every checkable problem becomes solvable.
Related event: P vs NP Explained: Why a Proof Could Break Modern Cryptography(2 posts)→
More from Research
- CMU's ExploitBench ranks LLM cyber agents on a capability ladder, not pass/fail — goyal__pramod · 2026-11-23
- Harvard paper: higher SWE-Bench scores didn't translate into more merged pull requests — rohanpaul_ai · 2026-11-23
- Princeton's SSoN Benchmark: Best Vision Model Scores 39.7% vs Human 83.3% on Spatial Consistency — jiqizhixin · 2026-11-23
- Four Color Theorem Was Exhaustion — This Lean Proof Is Different, Argues Mathematician — gleech · 2026-11-23
- Samsung Labs open-sources LittleBit, compressing LLM weights to 0.1 bits — MikePFrank · 2026-11-23
- Mathematicians Debate: Can 60GB of Lean Code Turn Into Real Understanding? — gleech · 2026-11-23