home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5151 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  2.3 KB
  1. Xref: sparky sci.crypt:5151 comp.theory:2499 sci.math:15343
  2. Newsgroups: sci.crypt,comp.theory,sci.math
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!news.udel.edu!udel!rochester!cantaloupe.srv.cs.cmu.edu!GS35.SP.CS.CMU.EDU!sgall
  4. From: sgall+@CS.CMU.EDU (Jiri Sgall)
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <By2tv0.BDn.2@cs.cmu.edu>
  7. Sender: news@cs.cmu.edu (Usenet News System)
  8. Nntp-Posting-Host: gs35.sp.cs.cmu.edu
  9. Organization: Carnegie Mellon University
  10. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <1992Nov18.193900.20199@rchland.ibm.com> <BxzD1t.3xA.2@cs.cmu.edu> <722273103@pike.cs.duke.edu>
  11. Distribution: inet
  12. Date: Sat, 21 Nov 1992 17:28:11 GMT
  13. Lines: 35
  14.  
  15. In article <722273103@pike.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
  16. |> In article <BxzD1t.3xA.2@cs.cmu.edu> sgall+@CS.CMU.EDU (Jiri Sgall) writes:
  17. |> >So if you know that P=NP, you also have a polynomial algorithm for SAT that 
  18. |> >either answers NO or gives you an satisfying assignment. You can do the same 
  19. |> >for anything in NP.
  20. |> 
  21. |> No, this is not true.   There are two *different* problems here:  knowing
  22. |> that P=NP, and having an algorithm for SAT (or any previously proved 
  23. |> NP-complete problem, for that matter).   Don't forget the perfectly valid 
  24. |> possibility that someone comes up with a non-constructive proof of P=NP --- 
  25. |> this would be amazingly frustrating though.  Imagine knowing that P=NP, so you
  26. |> know that polynomial time algorithms exist for all problems in NP,
  27. |> but you don't know a polynomial time algorithm for any problem previously
  28. |> shown to be NP-complete!  I think that's what the original poster probably
  29. |> meant.
  30.  
  31. And I was exactly arguing that it cannot get so bad. The first sentence was 
  32. supposed to read "you also know that there exists" instead of "you also have",
  33. sorry for the confusion. The rest of the argument is valid.
  34.  
  35. My claims are:
  36.  
  37. 1. I have an explicit algorithm for factoring which is polynomial if P=NP. 
  38. (No matter if you prove that nonconstructively.)
  39.  
  40. 2. I have an explicit algorithm that finds a satisfying assignement of a 
  41. satisfiable formula (but may run forever on an unsatisfiable one) if P=NP.
  42.  
  43. These claims are proved theorems (not by me), well known in the complexity
  44. community. They more or less say that ANY proof of P=NP has some strong
  45. consequences about concrete algorithms.
  46.  
  47. OK?
  48.  
  49. -- Jiri Sgall
  50.