home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15377 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  1.8 KB
  1. Xref: sparky sci.math:15377 sci.physics:19422
  2. Newsgroups: sci.math,sci.physics
  3. Path: sparky!uunet!cs.utexas.edu!tamsun.tamu.edu!snorkelwacker.mit.edu!galois!riesz!jbaez
  4. From: jbaez@riesz.mit.edu (John C. Baez)
  5. Subject: Re: RSA Encryption
  6. Message-ID: <1992Nov22.224208.12455@galois.mit.edu>
  7. Keywords: cryptography, primes
  8. Sender: news@galois.mit.edu
  9. Nntp-Posting-Host: riesz
  10. Organization: Department of Mathematics, Smogville, USA
  11. References: <avatarp.722363576@well.sf.ca.us> <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU>
  12. Date: Sun, 22 Nov 92 22:42:08 GMT
  13. Lines: 24
  14.  
  15. In article <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  16.  
  17. >Apropos of which, here is my proof that P=NP.  (I came up with it
  18. >around 1972, if you have an earlier source then it's not mine after
  19. >all.)  Computers double in speed every 18 months or so, whence any
  20. >exponential time problem can be solved in linear time by waiting the
  21. >requisite number of months for the problem to become solvable in one
  22. >month and then starting the computation.  This counts the waiting time,
  23. >and has the additional advantage that you can use your computer on
  24. >something else while waiting.
  25.  
  26. Very interesting.  Like Lewis Carroll's jokes, there is a real fact
  27. lurking in this one.  *If* the world's future was predictable in
  28. polynomial time from initial data, and *if* P was not equal to NP, one
  29. could use the contrapositive of Pratt's joke to prove that the rate of
  30. speed of computers cannot double each 18 months or so forever.
  31.  
  32. Of course, this assumes the world's future is deterministically
  33. predictable, which it's not, thanks to quantum mechanics.  (Please
  34. folks, don't mention chaos.  I'm sick of it.)  I leave it as an exercise
  35. for the reader to ponder what corrections need to be made to my previous
  36. paragraph to take quantum mechanics into account.
  37.  
  38.  
  39.