Re: Quantum Probability and Decision Theory

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

Brent Meeker wrote:
> On 31-Dec-02, Hal Finney wrote:
> > One correction, 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, one of the greatest
> > unsolved problems in computability theory.
>
> What about Hamiltonian circuits or factoring an integer or roots of a
> Diophantine equation?

I don't believe any of those are known to take exponential time. For all
we know a polynomial time solution may yet be found for all of these.

Hal
Received on Mon Dec 30 2002 - 20:15:13 PST