<p>The state-of-the-art for PCPs that yield a reduction to <span class="math-container">$(\frac{7}{8}+\varepsilon)$</span> 3-SAT (even for sub-constant <span class="math-container">$\varepsilon$</span>) are <a href="https://eccc.weizmann.ac.il//eccc-reports/2008/TR08-071/index.html" rel="noreferrer">those of Dana Moshkovitz and Ran Raz</a>, which have length <span class="math-container">$n^{1 + o(1)}$</span>. I do not know, however, if anyone tried to compute the exact dependence of the length on <span class="math-container">$\varepsilon$</span>, or the computation complexity of the reduction. Their main technical result was simplified later <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf" rel="noreferrer">by Irit Dinur and Prahladh Harsha</a>.</p>

<p>If you are interested in short PCPs with a constant number of queries that do not necessarily give optimal hardness-of-approximation reductions (a.k.a. "high-error PCPs"), then the state-of-the-art result is PCPs of length <span class="math-container">$n\cdot \mathrm{poly}\log n$</span> due to <a href="http://madhu.seas.harvard.edu/papers/2005/rspcpp-full.pdf" rel="noreferrer">Eli Ben-Sasson and Madhu Sudan</a> and its improvement by <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf" rel="noreferrer">Dinur</a>. Again, I do not know if anyone what is the exact complexity of computing the reduction.</p>

CC BY-SA 4.0
2018-10-31T00:25:08.840Z
Thank you; both parts were helpful.  I gather that quasilinear size PCP with O(1) queries and constant error remains an open problem.
Dmytro Taranovsky
CC BY-SA 4.0
2018-10-31T00:39:40.670Z
No, that actually follows from the work of Ben-Sasson and Sudan. It is an open problem to get such PCPs with sub-constant error.
Or Meir
CC BY-SA 4.0
2018-10-31T03:20:14.710Z
I looked some more and [Dinur 2007](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf) extends the paper you cited in the second paragraph to show $SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$.  If I understand correctly, this implies a reduction of 3-SAT to some quasilinear size $1-ε$ 3-SAT, but the result you cited in the first paragraph is nonredundant because it gives us $7/8+ε$ and more.
Dmytro Taranovsky
CC BY-SA 4.0
2018-10-31T09:01:41.090Z
Yes, that's correct. I forgot to mention Dinur's result, I'll add it to the answer.
Or Meir
CC BY-SA 4.0
2018-10-30T23:45:39.637Z
2018-10-31T09:02:45.960Z
2018-10-31T09:02:45.960Z
Or Meir
<p>What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs?  Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am especially interested in inapproximability of 3-SAT.</p>

<p>Let 7/8+ε-3-SAT be 3-SAT with the promise that if 7/8+ε fraction of the clauses are satisfiable, then the instance is satisfiable.  What are the best known reductions of 3-SAT with <span class="math-container">$n$</span> clauses to 7/8+ε-3-SAT?  For example, is there a reduction using <span class="math-container">$O(n \log n)$</span> clauses? (<span class="math-container">$O(n)$</span> clauses is an open problem.)  A reduction in uniform quasilinear size NC?  What is the dependence on <span class="math-container">$ε$</span>, including when <span class="math-container">$ε→0$</span>? Is there a known linear size (dependent on <span class="math-container">$ε$</span>) reduction of (1-ε)-3-SAT to 7/8+ε-3-SAT, and if not, do we have better bounds for (1-ε)-3-SAT?  Even a partial answer would be interesting.</p>

<p>Also, while it would perhaps make the question too broad, I should mention that another important issue here are the constant factors, which due to techniques like the long code are commonly infeasibly large.</p>

<cc.complexity-theory><reference-request><np-hardness><pcp>
Best known asymptotic PCP sizes / 3-SAT
Dmytro Taranovsky
# Best known asymptotic PCP sizes / 3-SAT

(Asked by: username_0 on 2018-10-30)

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am especially interested in inapproximability of 3-SAT.

Let 7/8+ε-3-SAT be 3-SAT with the promise that if 7/8+ε fraction of the clauses are satisfiable, then the instance is satisfiable. What are the best known reductions of 3-SAT with $n$ clauses to 7/8+ε-3-SAT? For example, is there a reduction using $O(n \log n)$ clauses? ($O(n)$ clauses is an open problem.) A reduction in uniform quasilinear size NC? What is the dependence on $ε$, including when $ε→0$? Is there a known linear size (dependent on $ε$) reduction of (1-ε)-3-SAT to 7/8+ε-3-SAT, and if not, do we have better bounds for (1-ε)-3-SAT? Even a partial answer would be interesting.

Also, while it would perhaps make the question too broad, I should mention that another important issue here are the constant factors, which due to techniques like the long code are commonly infeasibly large.

**Tags:** cc.complexity-theory, reference-request, np-hardness, pcp


---

## 1 answers

### Answer by username_1 on 2018-10-30. Score: 7 | Accepted answer

The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are [those of Dana Moshkovitz and Ran Raz](https://eccc.weizmann.ac.il//eccc-reports/2008/TR08-071/index.html), which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. Their main technical result was simplified later [by Irit Dinur and Prahladh Harsha](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf).

If you are interested in short PCPs with a constant number of queries that do not necessarily give optimal hardness-of-approximation reductions (a.k.a. "high-error PCPs"), then the state-of-the-art result is PCPs of length $n\cdot \mathrm{poly}\log n$ due to [Eli Ben-Sasson and Madhu Sudan](http://madhu.seas.harvard.edu/papers/2005/rspcpp-full.pdf) and its improvement by [Dinur](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf). Again, I do not know if anyone what is the exact complexity of computing the reduction.

> **Comments:**
> **username_0**: Thank you; both parts were helpful.  I gather that quasilinear size PCP with O(1) queries and constant error remains an open problem.  
> **username_1**: No, that actually follows from the work of Ben-Sasson and Sudan. It is an open problem to get such PCPs with sub-constant error.  
> **username_0**: I looked some more and [Dinur 2007](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf) extends the paper you cited in the second paragraph to show $SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$.  If I understand correctly, this implies a reduction of 3-SAT to some quasilinear size $1-ε$ 3-SAT, but the result you cited in the first paragraph is nonredundant because it gives us $7/8+ε$ and more.  
> **username_1**: Yes, that's correct. I forgot to mention Dinur's result, I'll add it to the answer.  

---

