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
- Shtetl-Optimized >> Blog Archive >> Ten Signs a Claimed Mathematical Breakthrough is Wrongscottaaronson.blog
- Computational Complexityblog.computationalcomplexity.org
- P versus NP problem - Wikipediaen.wikipedia.org
- Complexity Theory’s 50-Year Journey to the Limits of Knowledge | Quanta Magazinequantamagazine.org
- pnp.pdfscottaaronson.com
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Reasons to believescottaaronson.blog
- Random self-reducibilityen.wikipedia.org
- P vs. NP for Dummiesscottaaronson.blog
- Discovering cryptographic weaknesses with Claude \ Anthropicanthropic.com
- Complexity class - Wikipediaen.wikipedia.org
- What's new | Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Taoterrytao.wordpress.com