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.

  • $\begingroup$ You have copied an informal definition. Looking at the formal definition instead could clarify matters. $\endgroup$ Oct 23, 2019 at 7:32
  • $\begingroup$ @YuvalFilmus Which one is the formal definition? $\endgroup$
    – l4m2
    Oct 23, 2019 at 8:45
  • $\begingroup$ I understand it as "Both verifier and prover get the input, verifier is a TM with special functions that: send bit to prover(for unlimited times); generate random bits(for logorithm times); recieve bit from prover(for constant times), and verifier can be programmed to run for polynomial steps. Prover can do anything. Verifier can be programmed such that, if answer is TRUE, some prover always make verifier accept, and if answer is FALSE, all prover at least make verifier reject for half of time" $\endgroup$
    – l4m2
    Oct 23, 2019 at 8:56
  • $\begingroup$ The (somewhat) formal definition can be found on the same Wikipedia page, under Definition. $\endgroup$ Oct 23, 2019 at 9:10
  • 1
    $\begingroup$ The verifier runs in P, just like in the definition of NP. You could say the same about SAT. Does it also belong to P? $\endgroup$ Oct 23, 2019 at 9:51

1 Answer 1


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:

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

  • $\begingroup$ Currently I don't ask for a "proof", but only try to convince, so the amount of potential proofs doesn't matter $\endgroup$
    – l4m2
    Oct 22, 2019 at 22:36
  • $\begingroup$ Answers to different “routes” must be consistent, in the sense that they come from an underlying proof. This is part of the definition of PCP. You can’t make it go away. $\endgroup$ Oct 22, 2019 at 22:38
  • $\begingroup$ As I read, as long as in every round(where log(n) randomness and constant queries allowed) prover succeed, there's no info passing between rounds? How it mention the proof be consistent? $\endgroup$
    – l4m2
    Oct 22, 2019 at 23:10
  • $\begingroup$ Perhaps you should add your definition of PCP. In the usual definition there is only one round. $\endgroup$ Oct 23, 2019 at 5:01
  • $\begingroup$ In each round verifier see prover prove, it's more likely the statement is really true, but more rounds are needed to more convince, wrong? $\endgroup$
    – l4m2
    Oct 23, 2019 at 6:12

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.