home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5086 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  1.5 KB
  1. Xref: sparky sci.crypt:5086 sci.math:15306 comp.theory:2488
  2. Path: sparky!uunet!olivea!sgigate!sgi!wdl1!wdl39!mab
  3. From: mab@wdl39.wdl.loral.com (Mark A Biggar)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov20.190649.22570@wdl.loral.com>
  7. Date: 20 Nov 92 19:06:49 GMT
  8. References: <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com>
  9. Sender: news@wdl.loral.com
  10. Organization: Loral Western Development Labs
  11. Lines: 20
  12.  
  13. In article <1992Nov19.193036.26711@rchland.ibm.com> lwloen@vnet.ibm.com writes:
  14. >Surely, it can't be this easy.  I get squeamish whenever I see clocks and
  15. >numbers on arguments of this kind.  Is the cardinality of the set of
  16. >P algorithms == number of natural numbers?  Why doesn't Cantor's diagonal
  17. >argument crop up somewhere and spoil everything?  (I don't necessarily mean
  18. >the original, but an appropriate analog of it).
  19. >Or, does the cardinality N (that is, of natural numbers)
  20. >arise elsewhere in this problem?  I suppose some really smart people have
  21. >already covered this ground; it is all very counter to my intuition.  Maybe
  22. >it's time for me to take a class on all of this stuff. . .
  23.  
  24. The set of P-algorithms is a proper subset of the set of turing machines and
  25. the set of turing machines is countable, because by definition both the state
  26. set and the tape-symbol set for a turning machine are finite.
  27.  
  28. P-algorithms by definition halt with a known bound on running length.
  29.  
  30. --
  31. Mark Biggar
  32. mab@wdl1.wdl.loral.com
  33.