tag:blogger.com,1999:blog-6555947.post113945997721490532..comments2020-01-18T03:42:45.053-07:00Comments on The Geomblog: String theory and NP-hardnessSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-1139603925676990442006-02-10T13:38:00.000-07:002006-02-10T13:38:00.000-07:00This is a cool result. Instead of designing quant...This is a cool result. <BR/><BR/>Instead 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?<BR/><BR/> <BR/><BR/>  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1139525755105219562006-02-09T15:55:00.000-07:002006-02-09T15:55:00.000-07:00Hi Dave, thanks for the pointers: very interesting...Hi Dave,<BR/> thanks for the pointers: very interesting !! do you have any reference to these universality classes ?  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>SureshSureshhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1139513399503710402006-02-09T12:29:00.000-07:002006-02-09T12:29:00.000-07:00This reminds me that there is a cool example of wh...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. <BR/><BR/>Certainly 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?!)<BR/><BR/>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.)<BR/><BR/>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!<BR/><BR/>Good stuff!<BR/><BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://dabacon.org/pontiff" REL="nofollow" TITLE="dabacon at gmail dot com">Dave Bacon</A>Dave Baconhttp://dabacon.org/pontiffnoreply@blogger.com