1
$\begingroup$

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?

$\endgroup$
  • $\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 '17 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 '17 at 3:27
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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