Re: Quantum Probability and Decision Theory

From: Hans Moravec <hpm.domain.name.hidden>
Date: Mon, 30 Dec 2002 19:28:28 -0500

Hal Finney:
> there are no known problems which take
> exponential time but which can be checked
> in polynomial time. If such a problem could
> be found it would prove that P != NP ...

Communications glitch here. The definition
of NP is problems that can be solved in
polynomial time on a "nondeterministic"
machine, that is one that can test
simultaneously all candidate solutions
(effectively by creating exponentially
many processes for testing all possible
combinations of undetermined variables,
each individual combination taking polynomial
time to check)

A favorite example is the traveling
salesman problem (TSP), stated as "There is
a cycle of length no greater than L that
passes through all N nodes of this graph
exactly once." (True or False)

There are exponentially (in N) many cycles,
so determining if any one of them has
length less than L would seem to require
exponential time (barring some yet-
undiscovered P=NP trick)

But if an exponential solution finder
also returns, when it answers "True", a
cycle it found that had length <=L, that
answer can be checked in linear time: just
add up the arc distances.

It is conceivable that an efficient TSP
solver could correctly return "Yes" for a
given L without being able to identify a
winning cycle.

Checking that answer would then be no easier
than solving the original problem.

By the way, it is known that factoring into
primes is easier than the TSP. The discovery
of a classical polynomial time algorithm for
factoring would cause much less shock than
one for the TSP (which is "NP-complete",
the hardest class of NP problems. A polynomial
solution for any NP-complete problem can
be mapped into a polynomial solution for all
NP-complete problems, and thus all NP problems,
and factoring).
Received on Mon Dec 30 2002 - 19:33:04 PST