Impagliazzo's five worlds table resurfaces: which complexity universe do we live in?
matthew_d_green · x · 2026-11-08
Cryptographer Matthew Green reposts a table based on Impagliazzo's classic "five worlds" breakdown as a reminder that any of these complexity-theory universes is still possible:
- Algorithmica (P=NP): no crypto, but optimization, learning and proof search all become easy
- Heuristica (P≠NP, NP easy on average): no crypto; hard instances exist but are as hard to find as to solve
- Pessimoland: hard problems stay hard but no one-way functions — considered the worst world
- Minicrypt: one-way functions exist, no public-key encryption; hash signatures and AES survive, no key exchange
- Cryptomania: public-key encryption exists; lattices, hashes, AES; RSA/ECC fall to quantum (or classically if BPP=BQP)
The chart is being shared as a grounding reminder amid fast AI progress: we still don't know which world we're in.
More from Fun
- Starlink helps rescue five people stranded in Kazakhstan's snowy mountains — elonmusk · 2026-11-08
- Teen Beats OpenAI's Loading-Screen Snake Game Before the Image Finishes, Lands Internship — raidedclusteranimd · 2026-11-08
- Omarchy raises $10M foundation while Asahi contributors ask what they get — kingslyj · 2026-11-08
- Anthropic mascot Grady spotted in London as #whereisgrady tour continues — sarahookr · 2026-11-08
- Gary Marcus: Dario's 18-Month-Old Predictions Have Come Nowhere Close to Happening — GaryMarcus · 2026-11-08
- Running 4 AI Agents in Parallel and Still the Bottleneck: The Human — prasenx · 2026-11-08