Wait, he's saying that recognizing a proof in polynomial time makes finding a proof easy? The search space is exponential, and there's no adequate heuristic for a best-first search.
NP is the set of problems with solutions that are verifiable in polynomial time. If the problem size is n, imagine a non-deterministic Turing machine that can make one of 2 choices at each step. After n steps there are 2^n possible configurations of the machine, and your polynomial time verifier can check each of these configurations (in parallel, thanks to the non-determinism).
So there's n steps for the guessing and O(n^k) steps for the verification, so you've just been through an exponential search space in polynomial time.
That's why exponential search spaces are the bread and butter of NP. And also why many view P = NP as unlikely.
