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:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html#PRIMES
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