-----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-----
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
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 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).
participants (6)
-
Berzerk -
hughes＠ah.com -
Jim choate -
Jurgen Botz -
kkirksey＠world.std.com -
Perry E. Metzger