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?
I don't believe any of those are known to take exponential time. For all we know a polynomial time solution may yet be found for all of these. Hal
