NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
A non-deterministic Turing machine has a special instruction that allows it to non-deterministically "guess" a bit. The list of bits guessed by the machine is sometimes called a certificate. You can imagine that the guessed bits are taken from an auxiliary tape, whose contents you can think of as a certificate.

Here is an example. Consider the problem SAT: the input is a formula, and wish to find out whether the formula is satisfiable. A non-deterministic Turing machine for this problem "guesses" an assignment, and then checks ("verifies") that it satisfies the given formula. Alternatively, the machine gets a certificate and verifies that it is a satisfying assignment for the input formula. This is exactly the same Turing machine, only the process of non-deterministic guessing is visualized as reading from an auxiliary input, which we think of as a certificate.