# 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?

• No, it means that the length of the certificate is $O(f(n))$. Yes. Umm..., by running the certificate verification algorithm on its hint. – Ricky Demer Sep 10 '12 at 8:57
• Could you elaborate about the latter? – Ingrid Morstrad Sep 10 '12 at 9:16

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.

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"

• That's the usual way the proof is sketched (for example, on Wikipedia), but it omits the detail of how you keep the runtime bounded when the input should be rejected. – Ben Oct 10 '12 at 23:17
• @Ben: but the time complexity of a NDTM should depend only on the length of accepting computations (see my edit) – Vor Oct 11 '12 at 0:57
• Not all inputs have an accepting computation. The definition of NTMs that I'm aware of says that it is considered to accept if some path accepts, and reject if all paths halt in the reject state. If some paths reject and some don't terminate, then the NTM doesn't terminate. The trouble is in the equivalence of NTMs to DTMs you do a breadth-first search of the NTM's space. You can say it accepts as soon as you find an accepting path, but if you find a rejecting path you have to keep going because a longer path may accept. – Ben Oct 11 '12 at 1:21
• You need to explore all possible paths to prove that there isn't an accepting one if you're going to say the NTM rejects. – Ben Oct 11 '12 at 1:22
• In fact, I've just realised you could solve the halting problem with NTMs that are considered to halt and reject if they have a halting rejecting path. Have an NTM nondeterministically choose between rejecting immediately, and simulating the input TM, accepting if the TM accepts or rejects. That NTM will accept exactly when the input TM halts, and has a finite path leading to rejection even when the input TM doesn't halt. So an NTM that is considered to halt and reject under those conditions is strictly more powerful than a deterministic TM. – Ben Oct 11 '12 at 4:21

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).

• Can you elaborate about the later? Also, you said, "if a deterministic algorithm solves a problem ", but the deterministic algorithm only verifies the solution... – Ingrid Morstrad Sep 12 '12 at 4:00
• @IngridMorstrad deterministic in 'if a deterministic algorithm solves a problem' refers to a deterministic Turing machine algorithm. It can be used as a verifier by finding a solution and returning YES. – saadtaame Sep 12 '12 at 10:15
• I think you misunderstood my question. We have a verifier (a deterministic algorithm), I want to know how having a deterministic verifier assures that we have a non-deterministic solver. – Ingrid Morstrad Sep 14 '12 at 12:18
• @IngridMorstrad The verification stage of a non-deterministic solver is deterministic by definition. – saadtaame Sep 14 '12 at 15:03
• Actually, nondeterminism is not restricted to the guess&verify scheme. That's "only* a usual way to build NTMs for a given problem. – Raphael Oct 10 '12 at 20:07