home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5099 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.0 KB
  1. Xref: sparky sci.crypt:5099 sci.math:15318 comp.theory:2495
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!mcsun!sunic!dkuug!iesd!iesd.auc.dk!hans
  4. From: hans@iesd.auc.dk (Hans Huttel)
  5. Subject: Re: Cryptography and P=NP
  6. In-Reply-To: unruh@physics.ubc.ca's message of 20 Nov 1992 04:41:21 GMT
  7. Message-ID: <HANS.92Nov20230417@ravn.iesd.auc.dk>
  8. Summary: Sei nicht unruhig!
  9. Sender: news@iesd.auc.dk (UseNet News)
  10. Organization: Mathematics and Computer Science, Aalborg University
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu>
  12.     <1992Nov18.193900.20199@rchland.ibm.com> <BxzD1t.3xA.2@cs.cmu.edu>
  13.     <1ehq9hINN1e4@iskut.ucs.ubc.ca>
  14. Distribution: inet
  15. Date: 20 Nov 92 23:04:17
  16. Lines: 34
  17.  
  18.  
  19. In <1ehq9hINN1e4@iskut.ucs.ubc.ca> unruh@physics.ubc.ca (William
  20. Unruh) wrote:
  21.  
  22. > Could someone please remind us what P and NP mean? And what is being
  23. > varied to get "polynomial time" -- ie what is polynomial in time , or
  24. > what is time polynomial in?
  25.  
  26. In complexity theory, the time complexity of an algorithm is a
  27. function t: N --> N such that t(n) = m if the algorithm uses at most m
  28. steps on any input of length n. (In complexity theory "algorithm"
  29. usually means "multi-tape semi-infinite-tape Turing machine".)
  30.  
  31. So "polynomial time" means that the time complexity is a polynomial in
  32. n, n being the length of the input string. 
  33.  
  34. P is the class of problems that are solvable by a deterministic
  35. algorithm whose time complexity is polynomial. 
  36.  
  37. NP is the class of problems that are solvable by a _nondeterministic_
  38. algorithm whose time complexity is polynomial.
  39.  
  40. Since deterministic algorithms are special cases of nondeterministic
  41. ones, clearly P is contained in NP. The question of whether P = NP
  42. thus boils downs to determining whether or not nondeterminism is an
  43. essential feature [as far as complexity is concerned]
  44.  
  45. - Hans
  46.  
  47. --
  48. Hans H{\"u}ttel                          - hans@iesd.auc.dk  
  49. Mathematics and Computer Science
  50. Aalborg University, Fredrik Bajersvej 7E,
  51. 9220 Aalborg, DENMARK                     Ad slagne veje ?
  52.