Re: Quantum Probability and Decision Theory

From: Brent Meeker <>
Date: Mon, 30 Dec 2002 18:34:53 +0500

On 31-Dec-02, you wrote:

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

OK, you mean that *provably* take exponential time.

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

It seems it has been proven recently to be in P:

Brent Meeker
"One cannot guess the real difficulties of a problem before
having solved it."
   --- Carl Ludwig Siegel
Received on Mon Dec 30 2002 - 21:35:08 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST