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

Reply via email to