home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2773 < prev    next >
Encoding:
Text File  |  1992-12-31  |  4.4 KB  |  94 lines

  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!munnari.oz.au!metro!mama!naylor
  3. From: naylor@research.canon.oz.au (William Naylor)
  4. Subject: P != NP does NOT imply intractibility
  5. Message-ID: <C044Az.Lrp@research.canon.oz.au>
  6. Sender: news@research.canon.oz.au
  7. Organization: Canon Information Systems Research Australia
  8. Date: Thu, 31 Dec 1992 07:18:35 GMT
  9. Lines: 83
  10.  
  11. My recent thinking about randomized algorithms has reminded me of a simple
  12. fact that people seem to overlook:  even if somebody eventually 
  13. proves that P != NP, this does not imply the impossibility of physically 
  14. building a computing machine that can solve NP-complete problems 
  15. "in practice" in polynomial time.  The following paragraphs justify this
  16. assertion.
  17.  
  18. NP-completeness theory assumes that computation is accomplished on 
  19. Turing-machine equivalent computers; note that this rules out consultation
  20. with a random oracle and thus randomized algorithms are not permitted.
  21. An "algorithm" on such a computer must generate an answer, 
  22. together with a proof that the answer is correct.  Nothing less will
  23. suffice.
  24.  
  25. However, random oracles can be built physically, so assuming them away
  26. is unnecessarily pessimistic.
  27. It is possible to approximate a random oracle on a Turing-machine equivalent
  28. computer; and, according to our current understanding of physics, it
  29. is possible to physically build a true random oracle (using effects
  30. from quantum mechanics) and connect it to a Turing-machine equivalent 
  31. computer.  A "randomized algorithm" must do much less than a "deterministic
  32. algorithm" to effectively solve a problem:  a "randomized algorithm" 
  33. must generate
  34. an answer, which must be incorrect with probability <= P < 0.5 for some
  35. constant P.  This must hold for any problem instance.  Repeated calls
  36. to the randomized algorithm with the same problem instance can be used 
  37. to force the probability of error toward 0 (exponentially, 
  38. with the amount of computation).  Remember, a randomized algorithm can
  39. return different answers when presented the same problem instance
  40. twice.
  41.  
  42. The randomized algorithm need not generate a proof that
  43. the answer it returns is correct; it must only be possible to prove
  44. that the answer it returns is usually correct, for each and every
  45. problem instance.  This is a substantially weaker condition than
  46. that for Turing-machine algorithms.
  47.  
  48. Any proof that NP-complete problems cannot be solved in
  49. polynomial time on a physically realizeable computing machine must
  50. consider random oracles as well as Turing-machines.
  51.  
  52. There is some evidence, both empirical and theoretical, that randomized
  53. algorithms might be more powerful than deterministic algorithms.
  54.  
  55. The empirical evidence:  there exist some randomized algorithms that
  56. seem to perform better than any known deterministic algorithm.  The
  57. best example I know of is simulated annealing [1].  Perhaps the
  58. graph-isomorphism algorithm I have previously presented in comp.theory
  59. is also an example.
  60.  
  61. The theoretical evidence:  the problem of algorithm choice can be considered
  62. within the framework of 0-sum-2-person game theory [2].  Consider algorithm
  63. choice to be a game between the algorithm designer (who looks for a
  64. successful algorithm) and nature (who tries to find a problem instance
  65. which causes the algorithm to fail).  If every deterministic algorithm
  66. that the algorithm designer might choose has failure possibilities, then
  67. 0-sum-2-person game theory says that a "mixed strategy" is optimal for
  68. the algorithm designer; that is, he should randomly choose among his many
  69. algorithm possibilities rather than choosing a single algorithm.
  70.  
  71. Note that my remarks also apply to "undecideable problems" such as
  72. the halting problem.  Turing's proof that the halting problem cannot
  73. be solved on a Turing-machine does not imply that the halting problem
  74. cannot be effectively solved by a randomized algorithm.  
  75.  
  76. Does anybody out there know if it is known that the halting problem
  77. cannot be solved by a randomized algorithm?
  78.  
  79.  
  80. REFERENCES
  81.  
  82. [1]  Kirkpatrick S., Gelatt C. D., and Vecchi M. P.: "Optimization by
  83.      Simulated Annealing", Science 1983, #220, pages 671-680.
  84.  
  85. [2]  Sorry, I don't have a handy reference.  Any textbook on game theory
  86.      discusses this stuff.
  87.  
  88.  
  89. -- 
  90. Will Naylor               net:  naylor@research.canon.oz.au
  91.                           mail: Canon Information Systems Research Australia  
  92. phone: (61-2) 805-2921          P.O. Box 313 North Ryde, NSW 2113 
  93. fax:   (61-2) 805-2929          Australia
  94.