Theoretical Computer Science
cc.complexity-theory reference-request np-hardness pcp
Updated Sat, 28 May 2022 20:34:55 GMT

# Best known asymptotic PCP sizes / 3-SAT

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.

## Solution

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

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 and its improvement by Dinur. Again, I do not know if anyone what is the exact complexity of computing the reduction.

• +1 – I looked some more and Dinur 2007 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. — Oct 31, 2018 at 03:20