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)

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)

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 =(thesequentiallistofallelementsofthegroupwherea,b,andcbelongsto)$. 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 queries to its oracle:

• is the symbol belongs to the set of the group G? its oracle answers "yes" or "no".
• 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.

The confusing

In the properties section, we have

• 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)