🚀 go-pugleaf

I tried to send the following by E-mail, but the IBM gateway wouldn't
accept it....


In article <1992Nov19.193036.26711@rchland.ibm.com> you write:
>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.

Huh?  I can think of very, very few algorithms (programs) that can not
be counted on to halt.  The only simply stated one has the halting problem:
given a program, decide whether or not it will ever halt.  You will not
be able to guarantee that a program correctly solving this problem will
halt.  Other examples deal with word problems over certain algebras, but
not many people deal with that.  To re-iterate:  programs that cannot
be counted on to halt are very, very, very rare.  Most people will never
see one.

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

Yes, the cardinality of polynomial time algorithms is == the cardinality
of the natural numbers.  And you *can* use Cantor's diagonalization on
the set of P algorithms!  This is exactly how you show that there are 
algorithms (in fact, infinitely many of them) that are not in P.  This is the
"hierarchy theorem".  In fact, there many specific problems that you can
prove have no polynomial time algorithm (so the problem is not in P).
Unfortunately, these arguments simply do not work for separating P and
NP.  In fact, it has been shown that no diagonalization argument (ala
Cantor) will be able to separate P and NP --- regardless of how you try
to enumerate polynomial time algorithms. 


-- 
Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
Dept. of Computer Science  | above all other sciences, is that its laws are
Duke University     | absolutely certain and indisputable, while those of all
Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)