🚀 go-pugleaf

With regard to the question of whether a proof for P=NP would yield a
polynomial-time algorithm for NP problems,

sethb@fid.morgan.com (Seth Breidbart) writes:

>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.)

Yes, P=NP implies such a machine i exists.  But you might not be able
to prove it can recognize an NP-complete language, in spite of the
fact that it does.  In fact, you might not be able to prove of any
particular machine that it recognizes an NP-complete language in
polynomial time.

You might not even be able to prove of any particular polynomial that
it is the time bound for such a machine, even though you have proven
that the machine and the polynomial must exist.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil