From: tcmay@netcom.com (Timothy C. May)
Date: Tue, 19 Jul 94 10:52:30 PDT
To: nzook@math.utexas.edu
Subject: Re: GUT and P=NP
In-Reply-To: <9407191429.AA02051@vendela.ma.utexas.edu>
Message-ID: <199407191751.KAA23246@netcom4.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



> (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."