<p>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.</p>

<p>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&gt;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.</p>

<p>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).</p>

CC BY-SA 3.0
2014-03-11T20:56:02.810Z
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
vzn
CC BY-SA 3.0
2014-03-11T03:09:03.310Z
2014-03-11T15:11:37.277Z
2014-03-11T15:11:37.277Z
Michael Lampis
<p>The algorithm is as follows:</p>

<ul>
<li>If one of the constraints has no satisfying assignments, then output NO.</li>
<li>Otherwise, output YES</li>
</ul>

<p>Obviously this can be done in polynomial time.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-11T08:00:03.463Z
2014-03-11T08:00:03.463Z
Igor Shinkar
<p>along these lines a property relating PCP and NP can be found in the following citation p63 from <a href="http://www.unizar.es/acz/05Publicaciones/Monografias/MonografiasPublicadas/Monografia26/057Mayordomo.pdf" rel="nofollow">P vs NP</a> by Mayordomo (2004):</p>

<blockquote>
  <p>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 certiﬁcate bits
  (that is, the same number of bits for all inputs and certiﬁcates) and a logarithmic number
  of random bits, this is the complexity class PCP(log n, 1).</p>
</blockquote>

<p>the ref is:</p>

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

CC BY-SA 3.0
2014-03-12T16:32:48.923Z
_oops! reading [wikipedia](http://en.wikipedia.org/wiki/PCP_theorem), 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._
vzn
CC BY-SA 3.0
2014-03-10T23:30:40.973Z
2014-03-10T23:30:40.973Z
vzn
<p>I have seen this statement before, but I haven't really seen a proof of it:</p>

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

<p>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$?</p>

CC BY-SA 3.0
2014-03-10T15:52:06.840Z
Can you provide a link to where you saw this statement ?
Suresh Venkat
CC BY-SA 3.0
2014-03-11T21:43:13.997Z
plz define less well-known terms better or cite a ref that does. $PCP_{x,y}[\cdot], CSP[\cdot], GAP,$ etc... some on [PCP](http://en.wikipedia.org/wiki/PCP_theorem) thm wikipedia. note also wikipedia [states without citation](http://en.wikipedia.org/wiki/Probabilistically_checkable_proof#Properties): if NP ⊆ PCP[o(log n),o(log n)] then P=NP. also isnt this question literally asking how to prove P=NP?
vzn
CC BY-SA 3.0
2014-03-11T22:41:39.200Z
this related question [PCP characterization of NP](http://cstheory.stackexchange.com/questions/522/pcp-characterization-of-np) asks for outlook on whether PCP can be used somehow to separate P/NP with negative outlook/answers
vzn
CC BY-SA 3.0
2014-03-12T00:04:16.353Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2014-03-12T16:28:06.763Z
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](http://cstheory.stackexchange.com/help/how-to-ask) _be specific, give details and context_, and meta [states](http://meta.cstheory.stackexchange.com/a/507/7884) _provide background info_
vzn
<cc.complexity-theory><sat><pcp><p-vs-np>
If SAT is in PCP, for some constant q, then P = NP
matthon
# If SAT is in PCP, for some constant q, then P = NP

(Asked by: username_0 on 2014-03-10)

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$?

**Tags:** cc.complexity-theory, sat, pcp, p-vs-np

> **Comments:**
> **username_1**: Can you provide a link to where you saw this statement ?  
> **username_2**: plz define less well-known terms better or cite a ref that does. $PCP_{x,y}[\cdot], CSP[\cdot], GAP,$ etc... some on [PCP](http://en.wikipedia.org/wiki/PCP_theorem) thm wikipedia. note also wikipedia [states without citation](http://en.wikipedia.org/wiki/Probabilistically_checkable_proof#Properties): if NP ⊆ PCP[o(log n),o(log n)] then P=NP. also isnt this question literally asking how to prove P=NP?  
> **username_2**: this related question [PCP characterization of NP](http://cstheory.stackexchange.com/questions/522/pcp-characterization-of-np) asks for outlook on whether PCP can be used somehow to separate P/NP with negative outlook/answers  
> **username_3**: @username_2 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.  
> **username_2**: 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](http://cstheory.stackexchange.com/help/how-to-ask) _be specific, give details and context_, and meta [states](http://meta.cstheory.stackexchange.com/a/507/7884) _provide background info_  

---

## 3 answers

### Answer by username_4 on 2014-03-11. Score: 9

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

> **Comments:**
> **username_2**: 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  

---

### Answer by username_5 on 2014-03-11. Score: 3

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.


---

### Answer by username_2 on 2014-03-10. Score: -7

along these lines a property relating PCP and NP can be found in the following citation p63 from [P vs NP](http://www.unizar.es/acz/05Publicaciones/Monografias/MonografiasPublicadas/Monografia26/057Mayordomo.pdf) 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 certiﬁcate bits
> (that is, the same number of bits for all inputs and certiﬁcates) 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 veriﬁcation and the
hardness of approximation problems. Journal of the ACM, 45(3):501–555, 1998.

> **Comments:**
> **username_2**: _oops! reading [wikipedia](http://en.wikipedia.org/wiki/PCP_theorem), 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._  

---

