home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2521 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  2.3 KB
  1. Xref: sparky comp.theory:2521 sci.math:15440 sci.crypt:5215
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!usenet.coe.montana.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!TINMAN.OZ.CS.CMU.EDU!jmount
  3. From: jmount+@CS.CMU.EDU (John Mount)
  4. Newsgroups: comp.theory,sci.math,sci.crypt
  5. Subject: Re: Cryptography and P=NP
  6. Keywords: NP
  7. Message-ID: <By6yo0.173.2@cs.cmu.edu>
  8. Date: 23 Nov 92 23:02:24 GMT
  9. Article-I.D.: cs.By6yo0.173.2
  10. References: <BxvEF3.Kqw.2@cs.cmu.edu> <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1244@zogwarg.etl.army.mil>
  11. Sender: news@cs.cmu.edu (Usenet News System)
  12. Followup-To: comp.theory
  13. Organization: Carnegie Mellon University
  14. Lines: 33
  15. Nntp-Posting-Host: tinman.oz.cs.cmu.edu
  16.  
  17. In article <1244@zogwarg.etl.army.mil>, hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
  18. |> Yes, P=NP implies such a machine i exists.  But you might not be able
  19. |> to prove it can recognize an NP-complete language, in spite of the
  20. |> fact that it does.  In fact, you might not be able to prove of any
  21. |> particular machine that it recognizes an NP-complete language in
  22. |> polynomial time.
  23. |> 
  24. |> You might not even be able to prove of any particular polynomial that
  25. |> it is the time bound for such a machine, even though you have proven
  26. |> that the machine and the polynomial must exist.
  27. |> 
  28. |> Dan Hoey
  29. |> Hoey@AIC.NRL.Navy.Mil
  30.  
  31. Please see my post in sci.crypt (Message-ID:<By2v5F.DCM.2@cs.cmu.edu>, 
  32. Date: Sat, 21 Nov 1992 17:56:03 GMT) for a proof of how if P=NP you
  33. can build a machine that recognizes an NP Complete language (halts
  34. accepting on instances in the language, doesn't accept instances not
  35. in the language- but may not halt as in Garey&Johnson "Computers and
  36. Intractability: A guide to the Theory of NP-Completeness" 1979 pp.
  37. 24-25).  With only a proof that P=NP (you do not need to know the
  38. index of any machine that solves NP complete problems in poly time or
  39. even what the polynomial bounding some such machine is).
  40.  
  41. Of course this machine is SLOW, and you still have no idea how long it
  42. is going to take (only that it is less than some, unknown,
  43. polynomial).
  44.  
  45. -- 
  46. --- It is kind of strange being in CS theory, given computers really do exist.
  47. John Mount: jmount+@cs.cmu.edu               (412)268-6247
  48. School of Computer Science, Carnegie Mellon University, 
  49. 5000 Forbes Ave., Pittsburgh PA 15213-3891
  50.