Computational Complexity: Impagliazzo's Five Worlds
blog.computationalcomplexity.org · 210 words · saved by 3 readers
Boaz Barak in a comment last week mentioned one of my favorite survey papers, Russell Impagliazzo's A Personal View of Average-Case Complex...
Boaz Barak in a comment last week mentioned one of my favorite survey papers, Russell Impagliazzo's A Personal View of Average-Case Complexity presented at the 1995 Complexity Conference. In that paper he describes five possible worlds and their implications to computer science. Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. This was the world I described last week but looking back at Impagliazzo's paper, he does a nicer job. Heuristica: NP problems are hard in the worst case but easy on average. Pessiland: NP problems hard on average but…
saved by
related reading
- Reasons to believescottaaronson.blog
- 370.pdfeprint.iacr.org
- P versus NP problem - Wikipediaen.wikipedia.org
- World Models: Computing the Uncomputablenotboring.co
- Shtetl-Optimized >> Blog Archive >> Five Worlds of AI (a joint post with Boaz Barak)scottaaronson.blog
- P vs. NP and the Computational Complexity Zooyoutube.com
- Computational Complexityblog.computationalcomplexity.org
- P vs. NP for Dummiesscottaaronson.blog
- pnp.pdfscottaaronson.com
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- pasa.pdfmipmip.org
- An intensive introduction to cryptography: indexintensecrypto.org