🚀 go-pugleaf

In article <1992Nov18.193900.20199@rchland.ibm.com>
lwloen@vnet.ibm.com writes:
>In article <BxvEF3.Kqw.2@cs.cmu.edu> Jiri Sgall writes:
>
>>(partial quote of James Annan):
>
>>|> And remember, proving P=NP doesn't necessarily mean finding such an algorithm,
>>|> merely proving it exists.
>>|> 
>
>>Once you have the proof, you can easily run a kind of universal algorithm,
>>which will be guaranteed to be polynomial
>
>OK, I don't know beans about P and NP.  So, an elementary question:
>
>Do all programs of class P halt?  Your "universal algorithm" seems perilously
>close to the "halting" problem and I have never been able to eliminate it
>from far simpler cases than P or NP.  Or, is the halting issue kind of a
>separate point/issue (ie, the solution is "P" when it works)?

Each program in P runs in polynomial time, so it must halt.

Number all the polynomial-time machines (by adding a clock to each
Turing Machine); do this in such a way that machine k runs in time < n^k.
The "universal algorithm" consists of running machine i until it halts,
and checking to see if an answer is found.  If machine k solves the
problem, then this algorithm runs in time k n^k.  If P != NP, then
this universal machine might not halt.  (More likely, it will always
halt, but not within any polynomial time bound.)

Seth		sethb@fid.morgan.com