This is a basically computer program on A like a subroutine A such that for any input for the problem that is a "yes", there is a certificate C such that the size of C is polynomial in the size of x, and the verification algorithm will say "yes" but for any x that is a no, there is no certificate C that's polynomially sized with respect to x and the verification algorithm says "yes", so for any yes answer to the problem, a verification algorithm will say "yes" for some small certificate; otherwise, it'll say "no" for all small certificates. 