Length of the certificate in complexity classes
I'm a little confused by your quote.

There are two equivalent definitions of the NP complexity class in terms of Turing Machines:


The class of problems for which a deterministic verifier exists whose runtime is bounded by a polynomial in the size of the problem input.
The class of problems for which a nondeterminstic decider exists whose (nondeterministic) runtime is bounded by a polynomial in the size of the problem input.


So a nondeterministic machine trying to decide membership in a language wouldn't be presented with a certificate; that's not what it means to decide membership in a language. It's the deterministic verifier that gets a certificate - a verifier over language L is a decider over the language of pairs of an element of L and a certificate proving the element in L (that's why the definition is asymmetric and there's no certificates for non-membership; the verifier only answers "yes this is an element of L together with a certificate for this element", or "no this is either not an element of L or not a certificate for this element").

That aside, on to your questions.

If the running time of the verifier in O(f(n)), then the certificate (in general) is also in O(f(n)). It's possible the verifier needs to read the whole certificate and then do some trivial computation with it that doesn't increase the big-oh complexity over the time needed to simply read the certificate. Particular verifier algorithms for particular problems may well have much shorter certificates (implying that their runtime is occupied with much more computation than simply reading the certificate). But you can't say anything in general about an unknown verifier's certificate length just from knowing its runtime (well, anything more specific than that it's certificate length bound must be short enough to be read within its run time bound).

You also ask about how the existence of a deterministic verifier for a problem implies the existence of a nondeterministic decider for the same problem. The implication actually goes both ways (which is why the two definitions of the NP complexity class are equivalent).

Given a deterministic verifier you can construct a nondeterministic decider. The verifier is a decider over the language &lt;e, C(e)&gt; (where e is an element of L and C is a function that computes a certificate for e). The machine we're trying to construct will be given e as input. If it could come up with C(e) it could simply run the verifier on the pair and it would have its answer.

But our decider has the advantage of nondeterminism. It can simply guess a value for C(e) and run the verifier, and nondeterminism implies that if there is such a value that leads to acceptance then the machine will have picked the correct one. The "guessing" can be (almost) implemented by having a state that nondeterminsitically writes a symbol from the alphabet (any symbol) on the current cell, moves the tape head right, and then nondeterministically chooses to remain in the same state or to move on to the verifier stage.

Since the certificates must be within O(f(n)) length, and all we do before running the verifier is write down the certificate, the runtime of this machine on an e that is in L is O(f(n)) + O(f(n)), which is simply O(f(n)).

The only catch is that if e is not in L, then there is no such C(e) that will lead to the verifier accepting. But we can't let our machine keep trying longer and longer guesses for C(e); our machine is a decider, so it is required to halt for all input. The machine needs to know when to give up; it must only be capable of generating a finite number of guesses for C(e).

This means that machine must be able to calculate an upper bound to the length of C(e), and only guess strings up to that length. This means that the upper bound has to be a total computable function of e. I'm not 100% certain if that's possible in general for verifiers with completely arbitrary runtime complexity O(f(n)), because f might not be a computable function, and the exact certificate length can be larger than f(n) because of the details big-oh notation abstracts away from (constants, lower-order terms, and the fact that the bound only has to apply for sufficiently large n; maybe someone who knows a bit more can add something here). But for verifiers with polynomial big-oh complexity, there always exists a polynomial in n which is strictly larger than the minimum certificate length for any e with length n.

So we can presume the existence of a nondeterminstic machine which for an element e of length n, calculates this upper bound, guesses any string whose length is within the bound, and runs the verifier on it. Since guessing a string within a polynomial bound takes at most polynomial time, and the verifier had a polynomial run time bound, and the sum of two polynomials is still a polynomial, the nondeterministic decider always halts within a polynomial bound.

The other direction (the existence of a polynomial nondeterminsitic decider implies the existence of a polynomial deterministic verifier) is much easier. Let the certificate for any e in L simply be a record of all the transitions used by the nondeterministic decider when processing e. All the verifier has to do is check that this record forms a valid path through the nondeterministic decider leading to an accept state. Since checking this doesn't require exploring all the nondeterministic possibilities, a deterministic verifier can do this with overhead of a constant multiplier over the nondeterministic decider's runtime (it only needs to check each transition against the decider's set of possible transitions, which is a constant).

I've answered a slightly weaker question than you asked, however. I've only shown that you can come up with a decider for verifiers with a polynomial runtime bound (although similar reasoning applies to exponential bounds, and most other functions that actually get used very often when talking about big-oh complexity). I also haven't shown that a verifier with runtime in O(f(n)) implies the existence of a decider with runtime in O(f(n)), even for polynomial f; all I've shown is that if the runtime bound of the verifier is a polynomial then the runtime bound of the decider is still a polynomial; it might be larger one. I don't actually know whether a verifier always implies a decider with the same runtime bound; I'd welcome an addition from someone who knows for sure either way.