(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."
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
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
participants (5)
-
jamesd＠netcom.com -
m5＠vail.tivoli.com -
nelson＠crynwr.com -
nzook＠math.utexas.edu -
tcmay＠netcom.com