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$


  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?

  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Sep 2, 2017 at 7:56
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 3, 2017 at 3:27

1 Answer 1


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.

  • $\begingroup$ 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! $\endgroup$
    – Stav Alfi
    Sep 1, 2017 at 19:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – fade2black
    Sep 1, 2017 at 20:01
  • $\begingroup$ Thanks agian. Last question - Is a verifier by definition is deterministic TM? $\endgroup$
    – Stav Alfi
    Sep 1, 2017 at 21:23
  • 1
    $\begingroup$ Yes, it is deterministic by the definition of NP complexity class. $\endgroup$
    – fade2black
    Sep 1, 2017 at 21:24
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Sep 2, 2017 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.