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.


Reply via email to