Hal Finney:
I'm not sure if you are disagreeing with either of my statements above, that (1) there are no known problems which take exponential time but which can be checked in polynomial time, or that (2) if such a problem could be found it would prove that P != NP.
Ah, I see the communications glitch was at my end!
You were being precise: NP-complete is not known (for sure) to be exponentially hard, so NP-complete problems are not counterexamples to statement (1) But maybe (2) doesn't follow. There must be problems where checking some negative cases (in the TSP sense) takes more than polynomial time (maybe doesn't terminate), but positive answers can be checked in polynomial time. Those would fit the criteria, but not be in NP. (Trying to make one up ...)
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).
Right again, though apparently opinions differ about the unknowns: <http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node23.html> >> ... It is suspected but not yet known that factoring is NP-complete.
