Length of the certificate in complexity classes

Question

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?

Answer 1

I'm a little confused by your quote.

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

1. The class of problems for which a deterministic verifier exists whose runtime is bounded by a polynomial in the size of the problem input.

2. 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 <e, C(e)> (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.

Answer 2

Just a quick hint on how you can build the guess part of the non-deterministic solver, given a deterministic verifier (using ASCII art :)

         +----------------------+     +-----------------+
         |                      |     |                 |
         |               t1     V     V       t2        |
  [q2: write 0 on the ]<====[q1: START STATE]====>[q3: write 1 on the ]
  [certificate tape   ]           ||              [certificate tape   ]
                                  ||t3 
                                  \/ 
                       [q4: first state of the]
                       [deterministic verifier]
                            ........

Where t1,t2,t3 transitions (====>) represent nondeterministic choices

Using another informal notation:

1. nondeterministically pick one of the following steps:
   1.1. append a 0 to the certificate tape, and goto 1.
   1.2. append a 1 to the certificate tape, and goto 1.
   1.3. goto 2.
2. run the deterministic verifier using the input x and the certificate y as inputs

EDIT: (some clarifications)

1) for a Nondeterministic Turing machine (NDTM) there are infinite computations, one for each possible guessed string; some of them will halt on the accept state $q_Y$, some will halt on the reject state $q_N$, some will run forever;

2) a string $x$ is accepted by a Nondeterministic Turing machine if at least one of its computations halts on the accepting state $q_Y$;

3) a language $L_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$;

4) the definition of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:

$T_M(n) = max ( \{1\} \cup \{ m \; : \; $ there is an $x \in L_M$ such that $|x|=n$ and $M$ accepts $x$ in $m$ steps $\})$

The time complexity of a NDTM depends (by definition) only on the length of accepting computations.

See Garey&Johnson, "Computers and Intractability"

Answer 3

A non-deterministic Turing machine program $\mathcal{M}$ solves problems in two stages: (1) guess a candidate solution (certificate), (2) check that the guess is a solution. If it takes $\mathcal{O}(f(n))$ time to solve the problem, then the length of the certificate should be $\mathcal{O}(f(n))$ because you have to look at every bit of the certificate to validate it (if it's too long, just looking at it will take time that cannot be bounded by a function in $\mathcal{O}(f(n))$).

For the second part of your question, if a deterministic algorithm solves a problem in $\mathcal{O}(f(n))$ time, then you can use that same algorithm in the checking stage of the non-deterministic algorithm and ignore the guessing stage (don't look at the guessed solution).