home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5029 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  2.7 KB
  1. Xref: sparky sci.crypt:5029 sci.math:15261 comp.theory:2475
  2. Path: sparky!uunet!gatech!concert!duke!srt
  3. From: srt@duke.cs.duke.edu (Stephen R. Tate)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <722206613@pike.cs.duke.edu>
  7. Date: 19 Nov 92 20:56:54 GMT
  8. References: <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com>
  9. Followup-To: sci.crypt
  10. Organization: Duke University Computer Science Dept.; Durham, N.C.
  11. Lines: 41
  12.  
  13. I tried to send the following by E-mail, but the IBM gateway wouldn't
  14. accept it....
  15.  
  16.  
  17. In article <1992Nov19.193036.26711@rchland.ibm.com> you write:
  18. >Or is it, rather, P runs in polynomial time when it finds an answer?  I 
  19. >realise this is very basic, but I have yet to have encountered any significant
  20. >sub-set of programs that are not trivial that can be counted on to halt.
  21.  
  22. Huh?  I can think of very, very few algorithms (programs) that can not
  23. be counted on to halt.  The only simply stated one has the halting problem:
  24. given a program, decide whether or not it will ever halt.  You will not
  25. be able to guarantee that a program correctly solving this problem will
  26. halt.  Other examples deal with word problems over certain algebras, but
  27. not many people deal with that.  To re-iterate:  programs that cannot
  28. be counted on to halt are very, very, very rare.  Most people will never
  29. see one.
  30.  
  31. >Surely, it can't be this easy.  I get squeamish whenever I see clocks and
  32. >numbers on arguments of this kind.  Is the cardinality of the set of
  33. >P algorithms == number of natural numbers?  Why doesn't Cantor's diagonal
  34. >argument crop up somewhere and spoil everything?  (I don't necessarily mean
  35. >the original, but an appropriate analog of it).
  36.  
  37. Yes, the cardinality of polynomial time algorithms is == the cardinality
  38. of the natural numbers.  And you *can* use Cantor's diagonalization on
  39. the set of P algorithms!  This is exactly how you show that there are 
  40. algorithms (in fact, infinitely many of them) that are not in P.  This is the
  41. "hierarchy theorem".  In fact, there many specific problems that you can
  42. prove have no polynomial time algorithm (so the problem is not in P).
  43. Unfortunately, these arguments simply do not work for separating P and
  44. NP.  In fact, it has been shown that no diagonalization argument (ala
  45. Cantor) will be able to separate P and NP --- regardless of how you try
  46. to enumerate polynomial time algorithms. 
  47.  
  48.  
  49. -- 
  50. Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
  51. Dept. of Computer Science  | above all other sciences, is that its laws are
  52. Duke University     | absolutely certain and indisputable, while those of all
  53. Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)
  54.