-1
$\begingroup$

Show that any $S \in NP$ has 2 different polynomial-time verifiers $V_1, V_2$ such that, for all $x,y$, the following conditions hold:

  1. If $V_1(x,y)=1$ then $V_2(x,y)=0$
  2. If $V_2(x,y)=1$ then $V_1(x,y)=0$

I show a guideline that say to define $V_i(x,y)=1$ if $y=p(|x|)+i$ and there exists a prefix $y'$ of $y$ such that $V(x,y')=1$ but I'm confuse to find how it help to find the solution.

$\endgroup$
2
  • $\begingroup$ Can you add a bit more details to your question? What's $x$? what's $y$? Is $x$ an instance of some problem (i.e., a word of some language) and $y$ a certificate for that instance? Are $V_1$ and $V_2$ Turing machines? Do $V_1$ and $V_2$ need to run in polynomial-time (currently this is not requested by the question)? Is the part after "since" some sort of hint or you need to find two veryfiers that satisfy that property? It's immediate to show that any language $S \in \mathsf{NP}$ has infinitely many distinct verifiers. $\endgroup$
    – Steven
    Commented Apr 9, 2021 at 17:05
  • $\begingroup$ @Steven I editted, hope it's more clear now... After "since" we need to find two verifiers that satisfy that property, it's not a hint $\endgroup$ Commented Apr 9, 2021 at 17:10

1 Answer 1

1
$\begingroup$

Since $S \in \mathsf{NP}$, there is a non-deterministic poly-time Turing machine $T^*$ that decides $S$. Given $x \in S$, let $y^* = \langle y^*_1, y^*_2, \dots\rangle \in \{0,1\}^*$ be the list of non-deterministic choices of $T^*$ that lead to an accepting state in the execution of $T^*(x)$.

It is easy to see that $|y^*| = O(\mathrm{poly}(x))$ and that $y^*$ is a certificate for the the polynomial-time (deterministic) verifier $V^*$ that, with input $V^*(x,y^*)$, checks that the (unique) computation path of $T^*(x)$ when the non-deterministic choices are those in $y^*$ leads to an accepting state.

Define $y_1 =\langle 0, y^*_1, y^*_2, \dots \rangle$ and $y_2 =\langle 1, y^*_1, y^*_2, \dots \rangle$.

When $y=\langle y_0, y_1, y_2, \dots \rangle$, the verifier $V_i(x, y)$ behaves as follows: if $y_0 \neq i-1$, it rejects. Otherwise $V_i(x, y)$ simulates $V^*(x, \langle y_1, y_2, \dots\rangle)$ and accepts iff $V^*$ accepts. It is clear that $V_1$ and $V_2$ are polynomial-time verifiers for $S$ for the certificates $y_1$ and $y_2$, respectively. It remains to show that they satisfy the additional constraints from your question.

Notice that, if $V_1(x,y)$ accepts, then $y_0=0$, and hence $V_2(x,y)$ rejects since $y_0 = 0 \neq 1 = 2-1$. Similarly, if $V_2(x,y)$ accepts, then $y_0=1$, and hence $V_1(x,y)$ rejects since $y_0 = 1 \neq 0 = 1-1$.

$\endgroup$

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.