Computing the n-th Ramsey number R(n,n) is doable in exponential time. You can easily brute-force R(4, 4); a perfectly credible proof that takes exponential time! A credible proof must be verifiable in demonstrably finite time -- not necessarily polynomial.
Hard to find =/= hard to verify. Indeed that is the point of NP (which stands for "nondeterministic polynomial" time): solutions must be easy to check.