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.

Comments (4)

  • +0 – Thank you; both parts were helpful. I gather that quasilinear size PCP with O(1) queries and constant error remains an open problem. — Oct 31, 2018 at 00:25  
  • +0 – 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. — Oct 31, 2018 at 00:39  
  • +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  
  • +0 – Yes, that's correct. I forgot to mention Dinur's result, I'll add it to the answer. — Oct 31, 2018 at 09:01  

External Links

External links referenced by this document:

References