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