home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 5200 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  1.7 KB
  1. Path: sparky!uunet!stanford.edu!rock!concert!duke!srt
  2. From: srt@duke.cs.duke.edu (Stephen R. Tate)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Cryptography and P=NP
  5. Message-ID: <722537013@pike.cs.duke.edu>
  6. Date: 23 Nov 92 16:43:34 GMT
  7. References: <BxzD1t.3xA.2@cs.cmu.edu> <722273103@pike.cs.duke.edu> <By2v5F.DCM.2@cs.cmu.edu>
  8. Distribution: inet
  9. Organization: Duke University Computer Science Dept.; Durham, N.C.
  10. Lines: 24
  11.  
  12. In article <By2v5F.DCM.2@cs.cmu.edu> jmount+@CS.CMU.EDU (John Mount) writes:
  13. >Assume an enumeration of all Turing machines.  Suppose we want to
  14. >solve SAT.  Let ALG be the Turing machine that simulates one step of
  15. >machine i every 2^i steps (so it runs machine 1 every other step, 2
  16. >every 4th , 4 every 8th).
  17.  
  18. Ah...  very cute.  I'm not sure why I hadn't seen or didn't remember
  19. that construction.   Anyway, I hereby publically chastise myself for
  20. not seeing this.
  21.  
  22. Now a question:  decision problems in NP are shown to be NP-complete
  23. by many-to-one reductions, so the decision problems would all be
  24. solvable by this technique.  However, some optimization problems use
  25. Turing reductions, so you have to have an algorithm that always halts,
  26. even for negative instances (this construction does not halt in these
  27. cases).  Are there ways around this?  It seems that since verifying
  28. prime factors is in both NP and co-NP, that's the saving grace for
  29. factoring.  What about other problems?
  30.  
  31. -- 
  32. Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
  33. Dept. of Computer Science  | above all other sciences, is that its laws are
  34. Duke University     | absolutely certain and indisputable, while those of all
  35. Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)
  36.