GUT and P=NP

-----BEGIN PGP SIGNED MESSAGE-----
 
I was reading Hawking's _Black Holes & Baby Universes_ and an interesting
question struck me:  If a Grand Unified Theory exists, would it not 
prove P=NP to be true?
 
My Armchair Cosmologist's (TM) reasoning goes something like this:  If
a GUT exists, and that GUT is proven to be true (making it the Grand
Unified Law, I suppose), any behaviour we believe to be non-deterministic
really isn't: it obeys the GUL.  So P=NP must be true, since NP is
an artifact our pre-GUL way of looking at things.
 
Am I way off base here?  Can anyone with more knowledge in this area
than I tell me if I'm right, wrong, or somewhere in between?  Many
thanks,
 
Ken
 
=============================================================================
Ken Kirksey            kkirksey@world.std.com            Mac Guru & Developer
- -----------------------------------------------------------------------------
Harassment is a power issue, and power is neither male nor female.  Whoever
is behind the desk has the opportunity to abuse power, and women will take
advantage as often as men.               - Michael Crichton (in _Disclosure_)
 
-----BEGIN PGP SIGNATURE-----
Version: 2.6
 
iQCVAgUBLisd3+sZNYlu+zuBAQFIewP+Pailgh2SFHki+eakhVU9wRCX4kvTXGt/
A2cL/GdIAWkMTPDwOIjzG6MusXcyNUTnTIiAp+Ctzti2xa8F2hsyXU5yd8RQh6aE
ukmmKGvzYBocmiPV2ekl5aSlubV8+0BG4bLDDY5IKOwy1P+oXhY9539YumXuVq+D
xKp/7PdRBcU=
=Gx6j
-----END PGP SIGNATURE-----

question struck me:  If a Grand Unified Theory exists, would it not 
   prove P=NP to be true?

No.  Hardly.

   behaviour we believe to be non-deterministic
   really isn't: it obeys the GUL.  So P=NP must be true, since NP is
   an artifact our pre-GUL way of looking at things.

Non-determinism will exist forever as an idea, just the same way that
no real number has ever been measured, merely approximations to them.
NP is an expression of that idea.  There are other ways to formalize
NP without resorting to non-determinism.  NP is the class of problems
for which there exists a witness to a PTIME computation.
Non-determinism is only another way of rephrasing the existential
quantification.

Eric

Ken Kirksey says:
> I was reading Hawking's _Black Holes & Baby Universes_ and an interesting
> question struck me:  If a Grand Unified Theory exists, would it not 
> prove P=NP to be true?

No.

.pm

> 
> 
> Ken Kirksey says:
> > I was reading Hawking's _Black Holes & Baby Universes_ and an interesting
> > question struck me:  If a Grand Unified Theory exists, would it not 
> > prove P=NP to be true?
> 
> No.
> 
> .pm
> 
Ok Perry, I am not going to let you off that easily. Could you elucidate why
you feel that such a GUT would not solve this problem even in principle? If
a GUT could answer definitively whether there were a many-worls interpretation
this would definately address at least peripheral aspects of the P=NP problem.
It would also, necessarily, describe some limitations on computations and 
problem complexity. 

When one considers that there is no clear definition or proof of the exact 
solutions methods to prove P=NP it seems premature to posit such a definate
answer. While it might not be true that it would solve the problem in toto
it may be true that a clarification of the boundary conditions might make
the solution easier by reducing the number of choices of methodology one 
might look at.

I am interested on why you feel a GUT would have no effect, at least, on 
the boundary conditions of the problem?

Take care.

Jim choate says:
> Ok Perry, I am not going to let you off that easily. Could you elucidate why
> you feel that such a GUT would not solve this problem even in
> principle?

Because the question "does P=NP" is a question made with respect to an
abstract mathematical model that has nothing to do with the laws of
physics or the "real world". The models it is based on are complete in
and of themselves. Even in a Newtonian universe in which all things
are deterministic, the mathematical concept of a non-deterministic
Turing machine is possible. The notion that physics breakthroughs
might help the problem is based on a complete and utter ignorance of
the way mathematics works. It is as though one could show that the
concept of one half doesn't "work" because in the real world you can
never cut something perfectly in half.

The notion also shows a complete ignorance of automata theory and
its motivations. Turing machines are ALREADY impossible. They exist
only in mens minds.  A real Turing machine could never be built,
period, because they require infinite tapes. A Turing machine is a
MODEL of computation. The notion of a non-deterministic Turing machine
was never based on the concept that such a thing could actually exist,
but on the idea of asking the question "assuming one existed, what
could one do with one that one couldn't do with a "normal" Turing
machine." It is a common exercise in automata theory -- one sees
many exercises of the form "what could you do with an N head M tape
Turing machine, and how much faster can it compute". Did you suppose
that just because one can't build oracles for unsolvable problems that
the mathematics of oracles would suddenly disappear into the void?

> If a GUT could answer definitively whether there were a many-worls
> interpretation this would definately address at least peripheral
> aspects of the P=NP problem.  It would also, necessarily, describe
> some limitations on computations and problem complexity.

It would not have the least effect, any more than one could settle the
question of whether the continuum hypothesis is true.

Perry

On Tue, 19 Jul 1994, Perry E. Metzger wrote:
> Ken Kirksey says:
> > I was reading Hawking's _Black Holes & Baby Universes_ and an interesting
> > question struck me:  If a Grand Unified Theory exists, would it not 
> > prove P=NP to be true?
> No.
Unless *all* problems in the GUT were of class P and it was 
deterministic(ala bohm).  And if wishes were horses beggars would ride.

Roger, Never say never, Bryner.

Berzerk says:
> Unless *all* problems in the GUT were of class P and it was 
> deterministic(ala bohm).

That would make no difference. This tells us nothing about what
problems that are not in class P are like -- and our question is,
after all, if there are problems in NP that are not in P. The
determinism never even comes into play. Beyond that, the possibility
of such a mapping between P and GUT is so miniscule as to be
infinitesimal, and certainly has nothing to do with the question of
whether the universe is closed (which is what the original poster
suggested), especially since GUT doesn't predict the mass of the
matter in the universe and thus makes no prediction on openness or
closedness.

Perry

Ken Kirksey wrote:
> I was reading Hawking's _Black Holes & Baby Universes_ and an interesting
> question struck me:  If a Grand Unified Theory exists, would it not 
> prove P=NP to be true?

No.  For a couple of good arguments for this answer read the
``Mathematical Recreations'' column in the latest SciAm.  (Or 
maybe it was last month's).