home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2493 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.9 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!pacbell.com!pacbell!osc!jgk
  2. From: jgk@osc.COM (Joe Keane)
  3. Newsgroups: comp.theory
  4. Subject: Re: Cryptography and P=NP
  5. Summary: I'd bet that P=NP.
  6. Keywords: complexity
  7. Message-ID: <5856@osc.COM>
  8. Date: 19 Nov 92 03:16:04 GMT
  9. References: <PHR.92Nov15215202@napa.telebit.com> <1992Nov15.110945.19939@ringer.cs.utsa.edu> <15115@ember.UUCP> <Nov.16.16.59.47.1992.6436@remus.rutgers.edu>
  10. Reply-To: Joe Keane <jgk@osc.com>
  11. Organization: Versant Object Technology, Menlo Park, CA
  12. Lines: 52
  13. Weather: partly cloudy, high 66, low 50
  14. Moon-Phase: waning crescent (32% of full)
  15.  
  16. In article <Nov.16.03.59.05.1992.2368@remus.rutgers.edu>
  17. clong@remus.rutgers.edu (Chris Long) writes:
  18. >Anyone who believes P=NP is an idiot.
  19.  
  20. Well, count me in.
  21.  
  22. In article <Nov.16.16.59.47.1992.6436@remus.rutgers.edu>
  23. clong@remus.rutgers.edu (Chris Long) writes:
  24. >Sure, but P=NP and P<>NP are certainly not equally likely.  The a priori
  25. >evidence that P<>NP is *overwhelming*;
  26.  
  27. What evidence?!  What we have is literally hundreds of problems that occur
  28. naturally in a wide variety of subjects.  We've proven that these problems are
  29. all equivalent to each other (or maybe harder in some cases).  If anything,
  30. this makes it more likely that they're all in P than if they were independent.
  31.  
  32. For evidence, all i want is someone to show me *one* problem with a good
  33. argument why it's likely to be in NP\P.  I don't care if the problem occurs
  34. naturally or it's totally contrived.  So far i've not seen anything like this.
  35.  
  36. >to claim that P=NP has a chance of being true is worse than claiming that
  37. >there is a chance of only a finite number of twin primes existing.  Both are
  38. >unproven, but there are *very* strong reasons for believing them to be true.
  39.  
  40. No way; i think that the twin primes conjecture is very safe.  Most arguments
  41. from the P!=NP folks seem pretty lame, usually something like ``Well, if P=NP,
  42. it seems very weird to us, and we'd have to re-think a lot of stuff.''
  43.  
  44. >So strong that anyone who believes otherwise must be either ignorant or a
  45. >crackpot.
  46.  
  47. I'll take `crackpot', thanks.
  48.  
  49. In article <PHR.92Nov15215202@napa.telebit.com> phr@telebit.com (Paul Rubin)
  50. writes:
  51. >Most theorists think P!=NP, but some very sharp mathematicians think
  52. >factoring is in P.
  53.  
  54. This is an interesting example.  It's probably the simplest problem you can
  55. describe where it seems very hard to find a solution, but once found it's easy
  56. for anyone to verify.  Note that for a long time the best factoring algorithms
  57. ran in exponential time.
  58.  
  59. I think it's likely that we can factor in polynomial time, although i won't
  60. try to defend this either.  Anyway, i doubt that anyone's close to proving
  61. that it's impossible, which would prove that P!=NP.  Of course finding a
  62. polynomial factoring algorithm wouldn't prove that P=NP.  But it's some
  63. interesting evidence that things may not be as hard as they seem.
  64.  
  65. --
  66. Joe Keane, amateur mathematician
  67. jgk@osc.com (uunet!amdcad!osc!jgk)
  68.