🚀 go-pugleaf

In article <1992Nov19.172719.1540@fid.morgan.com>, sethb@fid.morgan.com (Seth Breidbart) writes:
|> 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.

Or is it, rather, P runs in polynomial time when it finds an answer?  I 
realise this is very basic, but I have yet to have encountered any significant
sub-set of programs that are not trivial that can be counted on to 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.)
|> 

Surely, it can't be this easy.  I get squeamish whenever I see clocks and
numbers on arguments of this kind.  Is the cardinality of the set of
P algorithms == number of natural numbers?  Why doesn't Cantor's diagonal
argument crop up somewhere and spoil everything?  (I don't necessarily mean
the original, but an appropriate analog of it).
  
Or, does the cardinality N (that is, of natural numbers)
arise elsewhere in this problem?  I suppose some really smart people have
already covered this ground; it is all very counter to my intuition.  Maybe
it's time for me to take a class on all of this stuff. . .

|> Seth		sethb@fid.morgan.com

-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer