# If $L_1,L_2\in \mathrm{NP}$ and $w\in L_1$ or $w\in L_2$ then can $L_1\cup L_2=L$'s verifier use the same certificate $c$ for $w$?

I read the following solution for Showing that $$\mathrm{NP}$$ is closed under union and they used the same $$c$$ for both the verifies $$V_1$$ and $$V_2$$. Why is it correct?

Let $$L_1$$ and $$L_2$$ be languages in $$\mathrm{NP}$$. Also, for $$i = 1, 2$$ let $$V_i(x, c)$$ be an algorithm that, for a string $$x$$ and a possible certificate $$c$$, verifies whether $$c$$ is actually a certificate for $$x \in L_i$$. Thus, $$V_i(x,c) = 1$$ if certificate $$c$$ verifies $$x \in L_i$$, and $$V_i(x, c) = 0$$ otherwise. Since both $$L_1$$ and $$L_2$$ are both in $$\mathrm{NP}$$, we know that $$V_i(x, c)$$ terminates in polynomial time $$O(|x|^d)$$ for some constant $$d$$. To show that $$L_3 = L_1 \cup L_2$$ is also in $$NP$$, we will construct a polynomial-time verifier $$V_3$$ for $$L_3$$. Since a certificate $$c$$ for $$L_3$$ will have the property that either $$V_1(x, c) = 1$$ or $$V_2(x, c) = 1$$, we can easily construct a verifier $$V_3(x, c) = V_1(x, c) \lor V_2(x, c)$$. Clearly then $$x \in L_3$$ if and only if there is a certificate $$c$$ such that $$V_3(x, c) = 1$$. Notice also that the new verifier $$V_3$$ will run in time $$O(2(|x|^d))$$, which is polynomial. Therefore, the union $$L_3$$ of two languages in $$\mathrm{NP}$$ is also in $$\mathrm{NP}$$, so $$\mathrm{NP}$$ is closed under union.

taken from here.

$$M_1,M_2$$ TM which accept $$w$$ can accept $$w$$ for different reasons so we can't claim that $$c_1=c_2$$

Questions:

1. Is it legal to use the same certificate for both $$V_1,V_2$$ in the answer? Why?

2. Is a verifier by definition is deterministic TM?

3. In the above answer, does $$V_3$$ runs $$x,c$$ on both $$V_1$$ and $$V_2$$ in the worst case?

• Depends. You can give two different, equivalent (w.r.t. computational complexity) definitions of the same problem that have incompatible certificates: it's all about encodings.
– Raphael
Sep 2, 2017 at 7:56
• We generally prefer that you ask only one question per post. Also, it would help to tell us your thoughts and what you have tried to resolve it on your own - for instance, question 2 is well-covered by standard definitions of NP.
– D.W.
Sep 3, 2017 at 3:27

Assume that $c_1$ and and $c_2$ are polynomial size certificates for $x \in V_1$ and $x \in V_2$. Then define $c=c_1\#c_2$, a new certificate formed by concatenation of $c_1$ and $c_2$ which is clearly polynomial size. Then $V_1$ and $V_2$ still can use $c$ as a certificate to verify $x\in V_1$ and $x\in V_2$. $V_1$ will use the left part of $c$ and the $V_2$ will use the right part of $c$.

Is a verifier by definition is deterministic TM?

Yes, the verifier is a deterministic TM, by definition.

In the above answer, does $V_3$ runs $x,c$ on both $V_1$ and $V_2$ in the worst case?

You can treat $V_3$ as a TM which invokes (as subroutines) $V_1(x,c)$ and $V_2(x,c)$, so if $V_1$'s worst case is $O(f)$ and $V_2$'s worst case is $O(g)$ then $V_3$'s worst case is either $O(f)$ or $O(g)$ which is polynomial.

• Thanks for the fast answer. Am I allowed to decide how my verifier will use $c$ ? Also you decided for a given $V1$ and $V2$ how they must use $c$ but you did not create $V1$ and $V2$. Why is that legal? (Also if you can, please refer to my other questions) I hope you understood what I'm trying to ask... Thanks! Sep 1, 2017 at 19:47
• In some way, yes, in fact you have to prove existence of such certificate and hence you decide on the structure of $c$. Also you have to prove the existence of $V_1$ and $V_2$, that use $c$ to verify membership of $x$. So, by assumption verifiers $M_{1}$ and $M_2$ together with certificate $c_1$ and $c2$ exists. You simply define a new certificate $c=c_1\#c_2$ and modify $M_1$ and $M_2$ (as $V_1$ and $V_2$) so that they use $c$ instead of $c_1$ and $c_2$ respectively. This proves existence of such verifiers and a certificate. Sep 1, 2017 at 20:01
• Thanks agian. Last question - Is a verifier by definition is deterministic TM? Sep 1, 2017 at 21:23
• Yes, it is deterministic by the definition of NP complexity class. Sep 1, 2017 at 21:24
• @StavAlfi The verifier can also be non-deterministic without changing the properties of the definition. However, it's rarely done because then the verification definition is no different from the acceptor definition, and hence not useful.
– Raphael
Sep 2, 2017 at 7:59