Quantum Computing since Democritus

by Scott Aaronson

The discovery of Cook, Karp, and Levin was not that there exist NP-complete problems – that's obvious – but rather that many natural problems are NP-complete.