home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.theory
- Path: sparky!uunet!munnari.oz.au!metro!mama!naylor
- From: naylor@research.canon.oz.au (William Naylor)
- Subject: P != NP does NOT imply intractibility
- Message-ID: <C044Az.Lrp@research.canon.oz.au>
- Sender: news@research.canon.oz.au
- Organization: Canon Information Systems Research Australia
- Date: Thu, 31 Dec 1992 07:18:35 GMT
- Lines: 83
-
- My recent thinking about randomized algorithms has reminded me of a simple
- fact that people seem to overlook: even if somebody eventually
- proves that P != NP, this does not imply the impossibility of physically
- building a computing machine that can solve NP-complete problems
- "in practice" in polynomial time. The following paragraphs justify this
- assertion.
-
- NP-completeness theory assumes that computation is accomplished on
- Turing-machine equivalent computers; note that this rules out consultation
- with a random oracle and thus randomized algorithms are not permitted.
- An "algorithm" on such a computer must generate an answer,
- together with a proof that the answer is correct. Nothing less will
- suffice.
-
- However, random oracles can be built physically, so assuming them away
- is unnecessarily pessimistic.
- It is possible to approximate a random oracle on a Turing-machine equivalent
- computer; and, according to our current understanding of physics, it
- is possible to physically build a true random oracle (using effects
- from quantum mechanics) and connect it to a Turing-machine equivalent
- computer. A "randomized algorithm" must do much less than a "deterministic
- algorithm" to effectively solve a problem: a "randomized algorithm"
- must generate
- an answer, which must be incorrect with probability <= P < 0.5 for some
- constant P. This must hold for any problem instance. Repeated calls
- to the randomized algorithm with the same problem instance can be used
- to force the probability of error toward 0 (exponentially,
- with the amount of computation). Remember, a randomized algorithm can
- return different answers when presented the same problem instance
- twice.
-
- The randomized algorithm need not generate a proof that
- the answer it returns is correct; it must only be possible to prove
- that the answer it returns is usually correct, for each and every
- problem instance. This is a substantially weaker condition than
- that for Turing-machine algorithms.
-
- Any proof that NP-complete problems cannot be solved in
- polynomial time on a physically realizeable computing machine must
- consider random oracles as well as Turing-machines.
-
- There is some evidence, both empirical and theoretical, that randomized
- algorithms might be more powerful than deterministic algorithms.
-
- The empirical evidence: there exist some randomized algorithms that
- seem to perform better than any known deterministic algorithm. The
- best example I know of is simulated annealing [1]. Perhaps the
- graph-isomorphism algorithm I have previously presented in comp.theory
- is also an example.
-
- The theoretical evidence: the problem of algorithm choice can be considered
- within the framework of 0-sum-2-person game theory [2]. Consider algorithm
- choice to be a game between the algorithm designer (who looks for a
- successful algorithm) and nature (who tries to find a problem instance
- which causes the algorithm to fail). If every deterministic algorithm
- that the algorithm designer might choose has failure possibilities, then
- 0-sum-2-person game theory says that a "mixed strategy" is optimal for
- the algorithm designer; that is, he should randomly choose among his many
- algorithm possibilities rather than choosing a single algorithm.
-
- Note that my remarks also apply to "undecideable problems" such as
- the halting problem. Turing's proof that the halting problem cannot
- be solved on a Turing-machine does not imply that the halting problem
- cannot be effectively solved by a randomized algorithm.
-
- Does anybody out there know if it is known that the halting problem
- cannot be solved by a randomized algorithm?
-
-
- REFERENCES
-
- [1] Kirkpatrick S., Gelatt C. D., and Vecchi M. P.: "Optimization by
- Simulated Annealing", Science 1983, #220, pages 671-680.
-
- [2] Sorry, I don't have a handy reference. Any textbook on game theory
- discusses this stuff.
-
-
- --
- Will Naylor net: naylor@research.canon.oz.au
- mail: Canon Information Systems Research Australia
- phone: (61-2) 805-2921 P.O. Box 313 North Ryde, NSW 2113
- fax: (61-2) 805-2929 Australia
-