Jump to content

Talk:Probabilistically checkable proof

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 91.79.59.157 (talk) at 18:58, 21 March 2016. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
WikiProject iconMathematics Start‑class Mid‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
StartThis article has been rated as Start-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-priority on the project's priority scale.
WikiProject iconComputer science Start‑class Mid‑importance
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
StartThis article has been rated as Start-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-importance on the project's importance scale.
Things you can help WikiProject Computer science with:

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

In the following It is claimed that 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. (In fact, non-determinism is not really needed here.) 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.


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)[reply]

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!

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]
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)[reply]
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)[reply]

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)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Probabilistically_checkable_proof&oldid=711244745"