principleMinor
How is $\text{PCP}[O(\log n),O(1)]$ NOT P?
Viewed 0 times
logtexthowpcpnot
Problem
As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.
For $\text{PCP}[O(\log n),O(1)]$, won't there just be polynomial many possible routes, and checking all just cost polynomial time?
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.
For $\text{PCP}[O(\log n),O(1)]$, won't there just be polynomial many possible routes, and checking all just cost polynomial time?
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.
Solution
A language $L$ is in $\mathsf{PCP}(r(n),q(n))$ if there is a randomized polytime algorithm $V(x,y)$ which acts as follows:
Furthermore, $V$ satisfies the following two conditions:
Let $n = |x|$. Since $V$ uses only $r(n)$ random bits and reads at most $q(n)$ bits of $y$, at most $2^{r(n)} q(n)$ bits of $y$ can potentially be read. when $r(n) = O(\log n)$ and $q(n) = O(1)$, this means that at most polynomially many bits are read from $y$, and so we can assume that $y$ has polynomial length.
Every language in $\mathsf{PCP}(O(\log n), O(1))$ is in $\mathsf{NP}$. Indeed, given $y$, we can compute $\Pr[V(x,y)\text{ accepts}]$ in polynomial time (since there are only polynomially many choices for the random bits). However, the language is not obviously in $\mathsf{P}$, since there are exponentially many choices for $y$.
- The algorithm is given $r(n)$ random bits.
- Given these random bits, it chooses (deterministically) $q(n)$ locations in $y$.
- It reads $y$ at these locations, and based on that, decides whether to accept or reject.
Furthermore, $V$ satisfies the following two conditions:
- If $x \in L$ then there exists $y$ such that $\Pr[V(x,y) \text{ accepts}] = 1$.
- If $x \notin L$ then for any $y$, $\Pr[V(x,y) \text{ accepts}] \leq 1/2$.
Let $n = |x|$. Since $V$ uses only $r(n)$ random bits and reads at most $q(n)$ bits of $y$, at most $2^{r(n)} q(n)$ bits of $y$ can potentially be read. when $r(n) = O(\log n)$ and $q(n) = O(1)$, this means that at most polynomially many bits are read from $y$, and so we can assume that $y$ has polynomial length.
Every language in $\mathsf{PCP}(O(\log n), O(1))$ is in $\mathsf{NP}$. Indeed, given $y$, we can compute $\Pr[V(x,y)\text{ accepts}]$ in polynomial time (since there are only polynomially many choices for the random bits). However, the language is not obviously in $\mathsf{P}$, since there are exponentially many choices for $y$.
Context
StackExchange Computer Science Q#116156, answer score: 3
Revisions (0)
No revisions yet.