Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $O(n)$ clauses be reduced to $(k,2k+1)$-SAT with $O(n)$ clauses (the constant may depend on $k$)?

3-SAT is NP complete, while 2-SAT and even $(k,2k)$-SAT are in P. $(k,2k+1)$-SAT for $k>1$ can be viewed as intermediate between 3-SAT and 2-SAT, and arguably as $2+ε$-SAT if $k$ is large. The paper (2+ε)-SAT is NP-hard proves that it is NP complete (see also a blog post; also, $(a,k)$-SAT is $(1,a,k)$-SAT in the paper). However, its proof goes through the PCP theorem and thus (given our lack of knowledge of linear size PCP) leaves open the question of whether the reduction can be done with a linear increase in the number of clauses. Specifically, their NP-completeness proof uses a gadget reduction from inapproximability of label cover. However, they only use local inapproximability rather than the full PCP theorem (they require satisfiability of label cover instances that are $ε$-satisfiable everywhere rather than just on average), which might make linear size more likely or easier.

The paper shows impossibility of a natural type of gadget reduction from 3-SAT: Given a 3-SAT clause using variables $x,y,z$, replace it with a conjunction of clauses using $x$,$y$,$z$ and internal variables, with $x$,$y$,$z$ remaining the only connection with clauses derived from other 3-SAT clauses. The problem is not in copying the inputs (using repeated variables in a clause, even $(k,2k)$-SAT allows variable copying), but is more deep. Given a putative encoding of a clause $x∨y∨z$, a simple numerical argument (proposition 4.5 in the linked paper) shows that if $(x,y,z)$ values $(1,0,0)$,$(0,1,0)$, and $(0,0,1)$ can all satisfy at least $k$ literals of every size $2k+1$ clause ($k>1$), then by taking the majority assignment of the internal variables (across the 3 assignments), $(0,0,0)$ also satisfies at least one literal of every such clause.

The above impossibility argument does not appear to work if we define gadgets more broadly. For example, instead of coding a 3-SAT variable $x$ by a single variable, we can code it by $O(1)$ variables (dependent on $k$). This way, an encoding of $x=0$ in a gadget for $x∨y∨z$ might depend on whether $y=0$, so averaging the encoding of $x$ across 3 assignments might produce a bad encoding. If desired, we can also code $x$ by a separate set of variables for every 3-SAT clause using $x$, using a copying gadget (if needed, with 3 inputs so that every variable is used by at most two gadgets) to connect the clauses.

The impossibility argument also does not appear to rule out a reduction from 3-SAT using a one-way deterministic finite state transducer, augmented with $O(1)$ slots for variable names, with the ability to read a variable name, output a variable name, and create a new variable name. (Another natural operation is testing two variable names for identity, but that should not be needed for a reduction from 3-SAT.)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.