1
$\begingroup$

Let $L$ be an $\mathrm{NP}$ language. Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if there exists a certificate $u \in \Sigma^{p(|x|)}$ for $x$ satisfying $V(x, u) = 1$.

Suppose that $\mathcal{V}_{q}$ be all the verifiers of $L$ such that the length of the certificates of $x$ is $q(|x|)$. And for every $V \in \mathcal{V}_{q}$, let $V_{x}$ be all the certificates of $x$.

For every polynomial $q\colon \mathbb{N} \to \mathbb{N}$ satisfying $\mathcal{V}_{q} \neq \varnothing$, I want to know whether there is a verifier $\bar{V} \in \mathcal{V}_{q}$ such that for every $x \in L$, $$\bar{V}_{x} = \bigcup_{V \in \mathcal{V}_{q}} V_{x}.$$

$\endgroup$

1 Answer 1

1
$\begingroup$

Fix $x \in L$ of length $|x|=n$. Suppose that $\mathcal{V}_q \neq \emptyset$, and let $m = q(n)$. Choose some $V^0 \in \mathcal{V}_q$. For any $s \in \{0,1\}^m$, let $V^s(y,u) = V^0(y,u \oplus s)$ for inputs of length $n$ and witnesses of length $m$, $V^s(y,u) = 0$ for inputs of length $n$ and witnesses lengths different from $m$, and $V^s(y,u) = V^0(y,u)$ otherwise. Then $V^s$ is a verifier for $L$ for all $s$, and so $\bigcup_{V \in \mathcal{V}_q} V_x = \{0,1\}^m$.

This means that if a verifier $\bar{V}$ exists, then $\bar{V}_x$ is the set of all strings of length $q(|x|)$. This means that $\bar{V}$ need not consult its witness, showing that $L \in \mathsf{P}$.

$\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.