GUT and P=NP

(flashing mathematical credentials)

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.

BUT, as I read it, this has _nothing_ to do with the P/NP question.  It simple
creates a new area of inquiry, the QP/QNP/QNP-complete area.  (The first qu
question being wheather some of these sets are empty.)  The P/NP question is
a question about Turing machines, and as such, would not be affected by the
creation of a non-Turing computer.


As for boundaries...  GUT _might_ give us a single equation that contains all
physical laws.  But so what?  We can't even solve the three-body problem for
gravity!  Chaos is an emergent process.

Have fun.

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

James A. Donald writes:
 > Existing physical theories show that Super Turing machines are
 > possible in principle though very difficult to build in practice.

That's the understatement of the year.

 > Such machines will probably not be able to solve NP complete
 > problems though they will be able to solve some NP problems
 > such as factoring.

Huh?

 > Since such machines do not operate algorithmically

This statement is exactly wrong.  Such machines *define* a class of
algorithms.

 > they have
 > no relevance to the question of whether P=NP, because this
 > question is a question about *algorithms*.

And this one.

| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

Mike McNally writes
> 
> 
> James A. Donald writes:
>  > Existing physical theories show that Super Turing machines are
>  > possible in principle though very difficult to build in practice.
> 
> That's the understatement of the year.

I was referring to the proposed quantum computers.

> 
>  > Such machines will probably not be able to solve NP complete
>  > problems though they will be able to solve some NP problems
>  > such as factoring.
> 
> Huh?
> 
>  > Since such machines do not operate algorithmically
> 
> This statement is exactly wrong.  Such machines *define* a class of
> algorithms.

I recommend that you read the following paper.

E. Bernstein and U. Vazirani, {\it Quantum Complexity
Theory}, Proc. 25th ACM Symp. on Theory of Computation, pp.  11--20
(1993).


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com

From: tcmay@netcom.com (Timothy C. May)
   Date: Tue, 19 Jul 1994 10:51:42 -0700 (PDT)

   > (flashing mathematical credentials)

   Who cares? I mean, really?

Because credentials are portable reputation.  A college is not a place
of higher learning, it's a reputation-granting institution.  A college
degree is no more valuable than the reputation it grants to you.  And,
once you establish your own reputation (as I have in my field), a
college degree becomes moot.  I wish colleges understood that.  I wish
students understood that.

This leads me to wonder how encryption helps make portable
reputations?  Can it even?

-russ <nelson@crynwr.com>    http://www.crynwr.com/crynwr/nelson.html
Crynwr Software   | Crynwr Software sells packet driver support | ask4 PGP key
11 Grant St.      | +1 315 268 1925 (9201 FAX)  | What is thee doing about it?
Potsdam, NY 13676 | LPF member - ask me about the harm software patents do.

Timothy C. May writes
> 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. 

Existing physical theories show that Super Turing machines are possible
in principle though very difficult to build in practice.

Such machines will probably not be able to solve NP complete
problems though they will be able to solve some NP problems
such as factoring.

Since such machines do not operate algorithmically, they have
no relevance to the question of whether P=NP, because this
question is a question about *algorithms*.

-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com