🚀 go-pugleaf

In article <1992Nov21.191944.87493@Cookie.secapl.com>
frank@Cookie.secapl.com (Frank Adams) writes:

>Given a problem which actually is in NP, this universal machine will in fact
>solve it in polynomial time if P=NP -- indeed, it will solve any problem in
>P, given an NP formulation, in polynomial time.  If the NP problem is in not
>in P, it will always halt, but will not necessarily run in polynomial time.

There is a problem with what you say here. Suppose we have a problem
formulated as an NP problem, but which is in fact in P. This
"universal" algorithm will indeed halt in polynomial time for the
cases for which the answer is "yes" (by finding the "non-deterministic
guess" required to show that the answer is indeed "yes"). If the
answer to the problem is "no", however, one may not know when to stop
looking for a positive answer. For it really to solve such a
problem-class in polynomial time, it has to have some rule for
determining when to say "no".

Keith Ramsay
ramsay@unixg.ubc.ca