home | literature reviews
Citation: Aaronson, Scott. "Guest column: NP-complete problems and physical reality." ACM Sigact News 36.1 (2005): 30-52.
Tags: Philosophical, Computer-scientific
This paper gives a delightful discussion of why the statement "NP-complete problems cannot be efficiently solved by physics" should be taken as a foundational physical law.
This gives a good gut-check for topological quantum computing: the quantum field computer can always be efficiently BQP-simulated. Perhaps if Freedman had read this article he would have been more skeptical about his claim in
> Freedman, Michael H. "P/NP, and the quantum field computer." Proceedings of the National Academy of Sciences 95.1 (1998): 98-101.
that TQFTs might be able to solve #P-complete problems.