home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15387 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.8 KB
  1. Xref: sparky sci.math:15387 sci.physics:19443
  2. Path: sparky!uunet!olivea!charnel!sifon!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!galois!riesz!jbaez
  3. From: jbaez@riesz.mit.edu (John C. Baez)
  4. Newsgroups: sci.math,sci.physics
  5. Subject: Re: RSA Encryption
  6. Keywords: cryptography, primes
  7. Message-ID: <1992Nov23.012510.14142@galois.mit.edu>
  8. Date: 23 Nov 92 01:25:10 GMT
  9. References: <avatarp.722363576@well.sf.ca.us> <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU> <1992Nov22.224208.12455@galois.mit.edu>
  10. Sender: news@galois.mit.edu
  11. Organization: MIT Department of Mathematics, Cambridge, MA
  12. Lines: 20
  13. Nntp-Posting-Host: riesz
  14.  
  15. In article <1992Nov22.224208.12455@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
  16. >In article <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  17. >
  18. >>Apropos of which, here is my proof that P=NP.  (I came up with it
  19. >>around 1972, if you have an earlier source then it's not mine after
  20. >>all.)  Computers double in speed every 18 months or so, whence any
  21. >>exponential time problem can be solved in linear time by waiting the
  22. >>requisite number of months for the problem to become solvable in one
  23. >>month and then starting the computation.  This counts the waiting time,
  24. >>and has the additional advantage that you can use your computer on
  25. >>something else while waiting.
  26. >
  27. >Very interesting.  Like Lewis Carroll's jokes, there is a real fact
  28. >lurking in this one.  *If* the world's future was predictable in
  29. >polynomial time from initial data, and *if* P was not equal to NP, one
  30. >could use the contrapositive of Pratt's joke to prove that the rate of
  31. >speed of computers cannot double each 18 months or so forever.
  32.  
  33. Whoops.  One only needs that polynomial time is not equal to exponential
  34. time, not that P is not equal to NP.  The former is known to be true.
  35.