Talk:Probabilistically checkable proof

PCP(r(n),q(n)) vs NTIME

The following was written: PCP[r(n), q(n)] ⊆ NTIME(2^(r(n))q(n)+poly(n)), if the verifier is constrained to be non-adaptive. I believe that the requirement of the verifier being non-adaptive is not necessary. Think of a non-deterministic machine that guesses all necessary bits from the proof pi. However, the machine needs to remember the accessed bits of pi to check for consistence. Otherwise, the verifier might accept inputs x that are not in the set. All this can be done in time poly(n, 2^(r(n)q(n)). See the book of Arora and Barak on page 242 Remark 11.6.3; although, they forget to mention the check for consistency and hence the polynomial increase in the NTIME complexity. — Preceding unsigned comment added by 91.79.59.157 (talk) 18:58, 21 March 2016 (UTC)

Mistakes ?

This following: If NP = PCP (o(log), o(log)) then NP = P Is a contradiction to the statement: NP = PCP (o(log), o(1))

It is indeed a contradiction, because the second statement is just false. NP = PCP(O(log),O(1)) is the correct statement, which the first statement doesn't contradict. --Robin (talk) 18:32, 20 August 2009 (UTC)

Dead link

During several automated bot runs the following external link was found to be unavailable. Please check if the link is in fact down and fix or remove it in that case!

• http://www.cs.jhu.edu/~scheideler/courses/600.471_S03/lecture_8.pdf
  • In PCP (complexity) on Mon Jul 17 14:21:25 2006, 403 Forbidden
  • In PCP (complexity) on Thu Jul 27 00:27:08 2006, 403 Forbidden

---

maru (talk) contribs 04:27, 27 July 2006 (UTC)

Strict Inclusion?

Maybe I'm missing something, but if NP = PCP(log, O(1)), then doesn't this imply that NP is a subset of PCP(log, poly), so it therefore can't strictly include PCP(log, poly) (By antisymmetricity of set inclustion)?

The original editor probably meant the symbol to just mean inclusion (instead of strict inclusion). I changed it to equality. Arbor 17:10, 5 September 2006 (UTC)

Sudarshan: Thats right... its an inclusion NP is a subset of PCP(log,C) —Preceding unsigned comment added by 220.227.207.12 (talk) 10:33, 25 December 2008 (UTC)

Merge?

I see no reason why this should be merged. Most major complexity classes have their own article, even those less imortant than PCP. The PCP article and the PCP theorem article are long enough to stand on their own, certainly. I suggest removing the tag unless there's some justification. CRGreathouse (t | c) 05:12, 8 October 2006 (UTC)

PCP and error correcting codes

Can someone include the details of PCP and error correcting codes here in this page... that seems to be an important work but is not cited anywhere. —Preceding unsigned comment added by 220.227.207.32 (talk) 10:39, 25 December 2008 (UTC)

Rename?

As a complexity class, PCP doesn't really stand alone, because it is the same as NP. But as a subtopic in theoretical computer science, we certainly need a separate article on PCP's and the PCP theorem. Would it be a good idea to move this article to probabilistically checkable proof (current a redirect to here)? That would I think better focus the article on PCPs as a technique and less focus it on PCP as a (nonexistent) independent complexity class. —David Eppstein (talk) 21:16, 19 December 2009 (UTC)

Is PCP even used as a complexity class without specifying randomness and queries? I've always seen stuff like PCP(log,O(1)), PCP(0, poly), etc. I would say that the PCP theorem asserts that NP = PCP(log, O(1)), rather than NP = PCP. --Robin (talk) 21:39, 19 December 2009 (UTC)

And to answer the original question, yes I agree that this article can be renamed so that it is about probabilistically checkable proofs in general. Then the article can mention the variety of classes you get from PCP(r,q), ranging from P to NEXP, and the most important class PCP(log, O(1)) which equals NP. --Robin (talk) 20:33, 23 December 2009 (UTC)

Ok, I went ahead and performed the rename. I haven't done much yet to edit the article, other than fixing the categories to match the new name, so if someone else wants to deal with that before I get around to it that would be great. —David Eppstein (talk) 21:34, 23 December 2009 (UTC)

I hope the article can have more text from the viewpoint in terms of proof and verification, and treating the complexity as one aspect of it. Jackzhp (talk) 11:05, 29 September 2018 (UTC)

Verifier's random bits

I've seen two definitions of PCPs, and I don't know which is the standard one. Is the verifier constrained to use his randomness only to make the queries, or can he use the randomness while deciding whether to accept or not? --Robin (talk) 13:49, 18 June 2010 (UTC)

do you mean the verifier tosses a coin, if it is head, then accept the statement and the proof, or if it is a tail, then reject the statement and the proof? Such a test procedure is irrelevant to the input. Jackzhp (talk) 11:08, 29 September 2018 (UTC)

There is no such thing "oracle access to a string" - oracle access is to a languages, not strings

79.181.73.211 (talk) 21:34, 11 April 2017 (UTC)

An oracle can represent any function from strings to binary values. Whether you interpret the binary values as describing membership of the string in a language, or whether you interpret the string as an index and the binary value as the proof bit at that index, is up to your interpretation, it is not part of the mathematics of the model. —David Eppstein (talk) 22:08, 11 April 2017 (UTC)

A simple example is needed

For example to prove a formula such as a+b=c, how could it be done with PCP? Jackzhp (talk) 07:05, 11 January 2018 (UTC)

I think such an example is meaningful for reader to understand better. Let me try:

The problem at hand is whether the statement "Given a,b,c, they satisfy the equation a+b=c under group G" is true? The equation can be much more complicated, and this is arithmetic satisfaction problem, just like Boolean satisfiability problem, it is an NP problem.

The design of the system highly depends on the problem at hand, and different design offers different properties. Suppose this is the background: A verifier does not have the knowledge of the group G. The Group_(mathematics) law could be pretty complicated such as a Galois fields on which an elliptic digital signature such as secp256k1 or [curve25519] is defined, while the integer addition group $\left(\mathbb {Z} ,+\right)$is simple. Though the verifier's oracle has the ability to act on the specific group law. That's to say it has the ability to check whether a given input belongs to the set of the group, and do group addition.

Then the following is a construction(design) for the system(I do not say this is a good design, but to give a concrete example):

A prover produces the proof $\pi$ is the sequential list of all elements of the group where a,b,and c belongs to. A Turing complete machine is able to produce such a proof suppose the set of the group is countable.

The input for the verifier is a sequence of symbols that are supposed to be elements of the group G.

The verifier does two types of queries to its oracle:

• is the symbol belongs to the set of the group G? its oracle answers "yes" or "no" after check the tape.
• under the group law G, a+b=?, its oracle answers s which is a+b, if both a & b are in the set of group G, otherwise answers "illegal query".

The verifier program: read a symbol from tape, ask its oracle whether it is in the group, if not reject the statement and the proof. If yes, check the next symbol, if yes, ask its oracle for the sum of the two. Upon response "illegal query", it rejects the statement; upon received s, the verifier check whether s==c, if yes, accept the statement and the proof; if s!=c, reject the statement and the proof.

In the above system, the oracle is doing search and linear group operation, so this is linear PCP. The completeness is 1, soundness is 0, the query complexity is 2*n-1, the random complexity is 0. any comment? Jackzhp (talk) 11:01, 29 September 2018 (UTC)

The confusing

In the properties section, we have the following text

• PCP[0, poly(n)] = NP (By the verifier-based definition of NP.)
• PCP[O(log n),O(1)] = NP (the PCP theorem)
• PCP[log n, poly(n)] = NP

This is confusing. Jackzhp (talk) 07:56, 29 September 2018 (UTC)

Date of proof?

The date of proof is listed as 1992, but all the inline references are 1998 publications. Googling for these papers is confusing, there might be an "unpublished" or "partially" published version in 1992 and a "very well published in ACM journal" version in 1998. Is that so? Is there a clearer source for the 1992 proof claim than the 1998 version? — Preceding unsigned comment added by 2800:2160:4400:170:C252:5FCD:FD06:EB11 (talk) 02:07, 25 June 2021 (UTC)

Mistake

The proof of the statement "On the other hand, if NP ⊆ PCP[o(log n),o(log n)] then P = NP." seems to be wrong. Mikkopitkonen (talk) 00:51, 12 March 2024 (UTC)

There is no such proof in our article. Do you perhaps mean that you think the JACM paper by Arora and Safra used as a reference for that statement is wrong? Or do you think we are misstating their claim? It can be found at the top of p.76 of their paper. —David Eppstein (talk) 01:08, 12 March 2024 (UTC)

I mean that the proof in their paper is wrong. I don't see how they get O(log n) size graph with polynomial number of reductions. 87.95.108.153 (talk) 01:28, 12 March 2024 (UTC)

Each reduction step reduces an $n$-vertex clique problem to an $n^{o(1)}$-vertex clique problem. Put another way, it acts on the logarithm of the number of vertices by $L\mapsto o(L)$. Expanding out the little-o notation, for all $\varepsilon >0$ there exists $L_{0}$ such that for $L>L_{0}$ it shrinks $L$ to less than $\varepsilon L$. Now take $\varepsilon ={\tfrac {1}{2}}$. With this choice, there exists $L_{0}$ such that in $\log _{2}L=\log _{2}\log n$ reduction steps it shrinks $L=\log n$ to $L_{0}$, reducing the number of vertices to $O(1)$. Before we reach that point we get a graph of size $O(\log n)$. I don't know why they stopped the iterated shrinking process at graphs of size $O(\log n)$ when they could have just said $O(1)$. —David Eppstein (talk) 02:12, 12 March 2024 (UTC)

Thank you for the nice proof. There is a little problem still: the $L_{0}$ is different for every reduction step. Mikkopitkonen (talk) 03:31, 12 March 2024 (UTC)

There is a single reduction algorithm from $n$-clique to $n^{o(1)}$-clique, with a single $L_{0}$ for $\varepsilon ={\tfrac {1}{2}}$, applied repeatedly. —David Eppstein (talk) 07:24, 12 March 2024 (UTC)

Yes, I see that now. This result would mean that BPP = P implies P = NP, but it seems to be not known. I would like to see the proof of the reduction, but I can't find the Theorem 26 they are citing. Mikkopitkonen (talk) 15:01, 12 March 2024 (UTC)

It would also mean that BPP = P implies that there is a polylog algorithm for solving the clique problems, but that would contradict the known lower bounds for clique complexity. Mikkopitkonen (talk) 16:37, 12 March 2024 (UTC)

Isn't Theorem 26 just the standard reduction from PCP to clique outlined in Clique problem § Hardness of approximation where we make a vertex for each possible run of the randomized proof checker and an edge for two runs that look like they're checking the same proof string? —David Eppstein (talk) 17:09, 12 March 2024 (UTC)

In that proof it says "It can be represented by a partial word with a 0 or 1 at each examined position and a wildcard character at each remaining position." so the size of the graph is not $n^{o(1)}$, it is bounded below by

${\binom {n}{o(\log n)}}$. Mikkopitkonen (talk) 18:42, 12 March 2024 (UTC)

There is only a vertex in the graph for each possible accepting run of a checker, not for combinations of symbols that no checker actually checks. So the number of vertices for PCP[a,b] is $2^{a+b}$ where $a$ is the number of random bits the checker flips to decide what to check, and $b$ is the number of proof bits that, when the checker examines them, could either be zero or one while still eventually leading to an accepting run. (Examining a bit that has only one valid state, and causes an immediate reject if anything else is seen, does not count.) This is fundamental to the approximation hardness of clique, not merely this specific question. If the reduction from PCP to clique produced superpolynomial sized graphs then it would not prove that clique is hard. —David Eppstein (talk) 19:24, 12 March 2024 (UTC)