Length of the certificate in complexity classes

A nondeterministic machine trying to decide membership in a language
is presented with a hint (called a "witness" or "certificate") which
proves membership (no such witness is provided for elements outside
the language; the definition is asymmetric).

So, if a non-deterministic algorithm can solve a problem in O(f(n)) time, does this mean the length of the certificate is f(n) [Since it could try all the possible combinations and the length of the shortest one will be f(n)]? And the input size is n?

Also, if a deterministic algorithm A exists that can verify a certificate in O(f(n)) time, how does this imply the existence of a non-deterministic algorithm that can solve the problem in O(f(n)) time?

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 ` (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 existe

StackExchange Computer Science Q#3494, answer score: 3