We study the computational complexity of the physical problem of finding vacua of string theory which agree with data, such as the cosmological constant, and show that such problems are typically NP hard.I mention this because it appears to be among the first few examples of NP-hardness impinging on the frontiers of physics. The paper has a very lucid explanation of some of the places in string theory where NP-hardness and other complexity notions pop up.
Some skepticism as to the relevance of this proof, here.
This reminds me that there is a cool example of where computability theory actually comes into the fronteirs of physics. This has to do with the classification of manifolds. It turns out that in four or higher dimensions, there is a classification problem for distinguishing diffeomorphic manifolds and, if I recall correctly, this computational problem is not computable. This means that the manifolds that are discussed in these higher dimensions can't even be distinguished by a computer. My understanding of why this doesn't apply to the case considered in this paper is that the manifolds considered are of a restricted class. Notably, however, I do believe this is a problem for theories which admit topology change of manifolds in higher dimensions.
ReplyDeleteCertainly also there has been a lot of work showing NP-hardness of solving certain physics problems, for example Barahona's work on the NP-completeness of the bounding the ground state energy of an random bond Ising model. In this setting some physicists have even learned what a PTAS is (okay it's mostly computer scientists who have written the papers about the physics problems, BTW!) Further questions about whether there are closed-time-like curves have relevance for NP-hardness. Also since non-linear quantum theories can be used to solve NP-complete problems efficiently, I'd argue that the whole black-hole information paradox is tied up with NP-completeness in a fundamental way. (Can we solve NP-hard problems by throwing half of an entangled state into a black hole?!)
That being said, I think physicists showing that a problem is NP-hard is good and I like the paper for this reason. I am also skeptical about the relevance of this result but need to read it more carefully.(And am glad to see that in a previous article the author of the link you point to corrects his NP=not polynomial statement.)
On a related note, there is something equivalent to complexity classes in condensed matter physics. Physicists call them universality classes: the fact that many different physical systems have very similar behaviors is often shown by mapping these problems onto each other in a way that preserves the physics of the problem. This is the equivalent, in many ways, to the notion of reductions between complexity classes!
Good stuff!
Posted by Dave Bacon
Hi Dave,
ReplyDeletethanks for the pointers: very interesting !! do you have any reference to these universality classes ?
Posted by Suresh
This is a cool result.
ReplyDeleteInstead of designing quantum computers that are unlikely to solve NP-hard problems efficiently, why don't physicists focus their research on string-theory computers! I see a new class: STP string-theory polynomial. Can we get the NSA to fund it?
Posted by Anonymous