Cristopher Moore
(University of New Mexico and the Santa Fe Institute)
P vs NP, Phase Transitions, and Incomputability in the Wild

Theoretical computer science concerns itself with complexity classes and their relationships; most famously, the P vs. NP problem, of whether solutions are easy to find whenever they are easy to check. P and NP are roughly analogous to the classes of decidable and recursively enumerable sets, since membership in an RE set can be confirmed in finite time. Sadly, we learned from Baker, Gill, and Solovay that the diagonalization argument of Turing and Church cannot possibly prove that P != NP. It was recently proposed that the behavior of random NP-complete problems near their phase transitions might shed some light on P vs. NP; but as I will discuss, 3-SAT and XORSAT have similar statistical properties, even though 3-SAT is NP-complete and XORSAT is in P.

I will end by commenting on incomputability in physics. It is easy to prove incomputability whenever we can engineer a computer out of tiles, atoms, or the like, but I suspect that many physical problems may be incomputable even when we cannot do this. In other words, I expect there are physical problems that are incomputable, but not Turing complete.