(flashing mathematical credentials)
Who cares? I mean, really?
Okay, I was hoping this would die quietly, but sinces it isn't....
GUT is a physical theory. If true, it is believed, it would be possible to manufacture a computer which excedes a Turing machine in several important ways. In particular, it is believed that a "quantum computer" could perform certain NP tasks (factoring) in P time.
Nope. A physical theory says nothing about this kind of stuff. It might, but it doesn't have to, which is the key issue. Suppose, for example, that the GUT (Grand Unified Theory) was Newtonian physics. Or Einsteinian GR. What could this possibly say about proving that P = NP? If the Really Truly Basic Unified Theory (RTBUT) is that subquark partons are scattering like billiard balls on a cosmic pool table, what could this possibly imply for theories of P = NP? Knowing that billiard ball physics is the RTBUT doesn't allow us to build computers that are really different from today's computers. Fact of life. Finding a solution to the shortest route between 50 cities is beyond current computer capabilitie, by many, many orders of magnitude. Doing it for 100 cities, or 10,000 cities, or as N increases further, will not made simple just because we learn in the year 2014 that gluons are made up of dentons and bound charmicles, all interacting via aptical foddering. Eric Hughes gave a mathematical perspective on this, I'm just giving a physics perspective. (Invoking quantum mechanics is something I'm avoiding discussing here, because it confuses things and may not be ultimately part of a GUT, logically. That's why I considered the less confusing example in which the RTBUT involved billiard ball scattering of sub-gluon or whatever particles. This GUT or RTBUT would _still_ not imply P = NP.) Another way to put it, there is no evidence, despite some speculation by Peter Shor, David Deutsch, Roger Penrose, and others, that any new theories of physics will allow "Super-Turing machines" to be built. In fact, most physicists discount this kind of speculation. Some of the work would need arbitrarily precise physical measurements, a situation not found in the real world....fits nicely with Eric's point about measuring the "reals"...real numbers in some sense have "infinite logical depth" and cannot be computed by any computer operating on discrete symbols....Smale at Berkeley has worked on the implications of building Turing machines with reals as the elements, and, indeed, amazing things happen, such as P = NP. But no such computer will be built in our universe, no matter what particles come flying out of the Super Duper Collider Looper. --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."