I have seen this statement before, but I haven't really seen a proof of it:

If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$.

Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, then SAT reduces to $GAP-q-CSP[1,2^{-q}]$. So to show $P = NP$, how do we show then that $GAP-q-CSP[1,2^{-q}]$ is in $P$?

  • 7
    $\begingroup$ Can you provide a link to where you saw this statement ? $\endgroup$ – Suresh Venkat Mar 10 '14 at 15:52
  • $\begingroup$ plz define less well-known terms better or cite a ref that does. $PCP_{x,y}[\cdot], CSP[\cdot], GAP,$ etc... some on PCP thm wikipedia. note also wikipedia states without citation: if NP ⊆ PCP[o(log n),o(log n)] then P=NP. also isnt this question literally asking how to prove P=NP? $\endgroup$ – vzn Mar 11 '14 at 21:43
  • $\begingroup$ this related question PCP characterization of NP asks for outlook on whether PCP can be used somehow to separate P/NP with negative outlook/answers $\endgroup$ – vzn Mar 11 '14 at 22:41
  • 7
    $\begingroup$ @vzn All these things are standard. Just check the chapter in Arora-Barak for definitions and the (easy) connections between PCPs, CSPs and GapCSPs. Your comments and answer are unnecessary. $\endgroup$ – Sasho Nikolov Mar 12 '14 at 0:04
  • $\begingroup$ SN se mgt aims for google-searchable results & making questions self-contained will help with that & also students looking for detail. not mandatory but "courtesy to reader". on other hand, tcs.se mgt has never expressed much concern for all that. your ref is halfway acceptable (again to an insider). se guidelines state be specific, give details and context, and meta states provide background info $\endgroup$ – vzn Mar 12 '14 at 16:28

Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done.

First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we know that the instance is not perfectly satisfiable and we are done). If a used predicate has two or more satisfying assignments, then, if we take a random assignment for all variables some constraint is satisfied with probability at least $2/2^q>1/2^q$. Since all other constraints are satisfied with probability at least $1/2^q$, by linearity of expectations there exists an assignment that satisfies strictly more than $1/2^q$ fraction of the constraints and we are done in this case.

Finally, suppose that all predicates used have exactly one satisfying assignment. Then the CSP is an instance of DNF-SAT, which can be decided in polynomial time (we only need to check if any two constraints have a conflict).

  • $\begingroup$ a P=?NP/PCP equivalence is significant, know any ref eg that goes into more detail? also this answer has no ref to PCP specifically/formally, suggest linking/connecting it with defn of PCP at least $\endgroup$ – vzn Mar 11 '14 at 20:56

The algorithm is as follows:

  • If one of the constraints has no satisfying assignments, then output NO.
  • Otherwise, output YES

Obviously this can be done in polynomial time.

For the analysis note that if one of the constraints has no satisfying assignments, then clearly the given instance is not satisfiable. Otherwise, if all constraints are satisfiable, then a random assignment satisfies each assignment with probability at least $2^{-q}$, and so, in expectation a random assignment satisfies at least $2^{-q}$ fraction of the constraints. This means that the value of the given CSP instance is at least $2^{-q}$, and by the gap assumption must be 1.


along these lines a property relating PCP and NP can be found in the following citation p63 from P vs NP by Mayordomo (2004):

The best known result [2] is that NP is exactly the class of problems that can be solved by probabilistic verifiers using a constant number of certificate bits (that is, the same number of bits for all inputs and certificates) and a logarithmic number of random bits, this is the complexity class PCP(log n, 1).

the ref is:

[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501–555, 1998.

  • $\begingroup$ oops! reading wikipedia, apparently regarded as a well known equivalence. however the Mayordomo ref has a few further ideas on the subj in a section, it is not common to cite PCP wrt P vs NP research/separation. $\endgroup$ – vzn Mar 12 '14 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.