🚀 go-pugleaf

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