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