Re: Quantum Probability and Decision Theory

From: Tim May <tcmay.domain.name.hidden>
Date: Mon, 30 Dec 2002 17:35:03 -0800

On Monday, December 30, 2002, at 03:46 AM, 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?

Hal will probably answer. I initially had the same reaction you had
(except only about Hamiltonian cycles and roots of Diophantines, but
not factoring, as factoring is not known to be NP-complete).

But upon rereading what Hal wrote, and what I had already drafted a
nearly complete reply to, I saw that he was making the subtle point
that there are "no known problems which take exponential time."

All of the NP-complete problems (Hamiltonian cycle, Diophantine, etc.)
currently only have exponential-time solutions. But there is no
guarantee that a polynomial solution (which is not NP, that is, is not
the result of a "guess" or an "oracle") will not be found sometime in
the future.

Proving that there "are" problems which can only be solved in
exponential time but which can be checked in polynomial time is subtly
different from saying that all problems in the class NP-complete admit
no polynomial time solutions.

(I'm trying to avoid using shorthand like P and NP and Exptime, as a
lot of confusion enters when shorthand gets misinterpreted.)


--Tim May
Received on Mon Dec 30 2002 - 20:37:55 PST