Re: Quantum Probability and Decision Theory

From: Hal Finney <hal.domain.name.hidden>
Date: Mon, 30 Dec 2002 17:23:52 -0800

Hans Moravec writes:

> 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)

I'm not sure if you are disagreeing with either of my statements above,
that (1) there are no known problems which take exponential time but
which can be checked in polynomial time, or that (2) if such a problem
could be found it would prove that P != NP.

> 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.

As I understand the state of play, factoring into primes is not known
to be NP-complete, but the contrary is not known, either. Factoring is
strongly suspected not to be NP-complete but that has not been proven.
So it is still possible that factoring into primes is just as hard as
the TSP, although it is thought to be unlikely (it would imply that
NP = coNP).

Hal Finney
Received on Mon Dec 30 2002 - 20:25:04 PST