home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5064 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.0 KB
  1. Path: sparky!uunet!gatech!concert!duke!srt
  2. From: srt@duke.cs.duke.edu (Stephen R. Tate)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Cryptography and P=NP
  5. Message-ID: <722273385@pike.cs.duke.edu>
  6. Date: 20 Nov 92 15:29:46 GMT
  7. References: <1992Nov19.193036.26711@rchland.ibm.com> <722206613@pike.cs.duke.edu> <1992Nov20.100712.7550@nntp.nta.no>
  8. Organization: Duke University Computer Science Dept.; Durham, N.C.
  9. Lines: 33
  10.  
  11. In article <1992Nov20.100712.7550@nntp.nta.no> klaus@hal.nta.no (Klaus Gaarder FNI) writes:
  12. >In article <722206613@pike.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
  13. >|> To re-iterate:  programs that cannot
  14. >|> be counted on to halt are very, very, very rare.  Most people will never
  15. >|> see one.
  16. >
  17. >Unless Mr Tate has a fairly restriced view of 'programs' I must say:
  18. >
  19. >"Surely you're joking Mr Tate?"...
  20. >
  21. >I DO hope my Unix instance never halts...so 
  22. >in fact most computer users see a program never halting EVERY SINGLE DAY,
  23. >namely their favourite OS!!
  24.  
  25. Ok, ok.  Several people have pointed things like this out to me.  But
  26. remember the context of my comment.  We're talking about P vs. NP, and
  27. algorithms for decision problems.  In other words, the entire point of
  28. running the algorithm is to arrive at a single answer.  In fact, most
  29. definitions of algorithm include the condition that the algorithm halt
  30. in a finite amount of time.   An OS may not halt, but it's not a program
  31. designed to get an answer, and is not in the least considered an
  32. "algorithm" in the sense of algorithms studied for complexity theory.
  33.  
  34. I used the term "program" rather than algorithm trying to be informal,
  35. and because it's what the original poster used.  I suppose it was a
  36. mistake....
  37.  
  38.  
  39. -- 
  40. Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
  41. Dept. of Computer Science  | above all other sciences, is that its laws are
  42. Duke University     | absolutely certain and indisputable, while those of all
  43. Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)
  44.