Even I went “Huh?!” when I read the abstract of this paper titled [[http://www.scottaaronson.com/papers/npcomplete.pdf|NP-complete Problems and Physical Reality]] by [[http://www.scottaaronson.com|Scott Aaronson]]. Here’s the abstract for your benefit:

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and “anthropic computing.” The section on soap bubbles even includes some “experimental” results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

This paper had been lying around on my TODO list for a really long time now. So on my (loooooooong) flight back from Australia, I finally decided to get it over with. It was a really interesting read, though I’m sad to report that I didn’t really understand most of the paper. The theme of the paper is very speculative: are there physical processes in nature that might not follow the Turing model of computation that we’re used to, and there by perhaps open up the possibility of attacking problems that are intractable for Turing machines.

I’m not a theory person, but I still found the paper really interesting. I mean, computation is such a deep and beautiful concept (as characterized by Turing machines) but I don’t think about it on a daily basis. So it was refreshing to read about it. And it made me realize that I need to brush up on my complexity theory as well :-(

There’s a lot of complexity and quantum physics/computing references in the paper. So if you’re into those areas, definitely give the paper a read (and let me know if you can help explain some sections to me!).