If $L_1,L_2\in 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 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 $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 $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 $V3$ 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 $NP$ is also in $NP$, so $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 $V3$ 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 '17 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 '17 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! – Stav Alfi Sep 1 '17 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. – fade2black Sep 1 '17 at 20:01
• Thanks agian. Last question - Is a verifier by definition is deterministic TM? – Stav Alfi Sep 1 '17 at 21:23
• Yes, it is deterministic by the definition of NP complexity class. – fade2black Sep 1 '17 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 '17 at 7:59