On Monday, December 30, 2002, at 03:46 AM, Brent Meeker wrote:
Hal will probably answer. I initially had the same reaction you had (except only about Hamiltonian cycles and roots of Diophantines, but not factoring, as factoring is not known to be NP-complete).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?
But upon rereading what Hal wrote, and what I had already drafted a nearly complete reply to, I saw that he was making the subtle point that there are "no known problems which take exponential time."
All of the NP-complete problems (Hamiltonian cycle, Diophantine, etc.) currently only have exponential-time solutions. But there is no guarantee that a polynomial solution (which is not NP, that is, is not the result of a "guess" or an "oracle") will not be found sometime in the future.
Proving that there "are" problems which can only be solved in exponential time but which can be checked in polynomial time is subtly different from saying that all problems in the class NP-complete admit no polynomial time solutions.
(I'm trying to avoid using shorthand like P and NP and Exptime, as a lot of confusion enters when shorthand gets misinterpreted.)
--Tim May
