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 ...
Communications glitch here. The definition of NP is problems that can be solved in polynomial time on a "nondeterministic" machine, that is one that can test simultaneously all candidate solutions (effectively by creating exponentially many processes for testing all possible combinations of undetermined variables, each individual combination taking polynomial time to check)
A favorite example is the traveling salesman problem (TSP), stated as "There is a cycle of length no greater than L that passes through all N nodes of this graph exactly once." (True or False) There are exponentially (in N) many cycles, so determining if any one of them has length less than L would seem to require exponential time (barring some yet- undiscovered P=NP trick) But if an exponential solution finder also returns, when it answers "True", a cycle it found that had length <=L, that answer can be checked in linear time: just add up the arc distances. It is conceivable that an efficient TSP solver could correctly return "Yes" for a given L without being able to identify a winning cycle. Checking that answer would then be no easier than solving the original problem. By the way, it is known that factoring into primes is easier than the TSP. The discovery of a classical polynomial time algorithm for factoring would cause much less shock than one for the TSP (which is "NP-complete", the hardest class of NP problems. A polynomial solution for any NP-complete problem can be mapped into a polynomial solution for all NP-complete problems, and thus all NP problems, and factoring).