# Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

Let the variables be $x_1 , x_2 , x_3 ... x_n$. The distance between two variables is defined as $d(x_a , x_b) = |a-b|$. The distance between two literals is the distance between the corresponding two variables.

Suppose I have a 3-SAT instance such that for every clause $(x_a , x_b, x_c)$ we have $d(x_a , x_b) \leq N \wedge d(x_a , x_c) \leq N \wedge d(x_b , x_c) \leq N$ for some fixed value $N$.

Conceptually you can picture this as all the literals being physically on a line and all the clauses are incapable of reaching beyond a certain length for physical reasons.

Given this constraint are there any hard instances of 3-SAT? How small can I make the neighborhood and still find hard instances? What if I allow a few clauses to violate the constraint?

By hard I mean a heuristic solver would fall back on the worst case.

• "By hard I mean a heuristic solver would fall back on the worst case." doesn't sound well-defined to me. Can we interpret your question as asking whether there is a polynomial-time algorithm that solves all such 3-SAT instances? Or asking about the complexity/hardness of this problem?
– D.W.
Commented Jul 10, 2018 at 1:57
• "Can we interpret your question as asking whether there is a polynomial-time algorithm that solves all such 3-SAT instances?" I think that's what I'm looking for. Commented Jul 10, 2018 at 2:40
• The locality requirement you are using is also known as 1D "geometrically local" and is the predominant meaning of "locality" for physicists. Now, if one generalizes your question to the quantum case and from bits (2 states) to particles with 8 states, the quantum version of your problem is indeed QMA-complete ("quantum-NP") in 1D: See arxiv.org/abs/1312.1469 For qubits the problem is QMA-complete in 2D. arxiv.org/abs/quant-ph/0504050 Commented Jul 10, 2018 at 7:37
• Ah so its true a physicist can't hide among computer scientists. You caught me. Why do you need 8 states? Just use qubits, triple the neighborhood size, and use every 3 qubits to encode an 8-state particle. Commented Jul 10, 2018 at 8:18
• Sure, but then you've got quite high locality, i.e. your local operators span many qubits. This line of research has also focused on minimizing locality (ideally 2-local) at the cost of higher-dimensonal particles and the trade-offs involved. Commented Jul 10, 2018 at 8:26

No. If the 3-SAT instance has $m$ clauses, then you can test satisfiability in $O(m 2^N)$ time. Since $N$ is a fixed constant, this is a polynomial-time algorithm that solves all instances of your problem.
The algorithm works in $m$ stages. Let $\varphi_i$ denote the formula consisting of the clauses that use only variables from $x_1,\dots,x_i$. Let $S_i \subseteq \{0,1\}^n$ denote the set of assignments to $x_{i-N},x_{i-N+1},\dots,x_i$ that can be extended to a satisfying assignment for $\varphi_i$. Note that given $S_{i-1}$, we can compute $S_i$ in $O(2^N)$ time: for each $(x_{i-N-1},\dots,x_{i-1}) \in S_{i-1}$, we try both possibilities for $x_i$ and check whether it satisfies all clauses from $\varphi_i$ that contain the variable $x_i$; if so, we add $(x_{i-N},\dots,x_{i})$ to $S_i$. In the $i$th stage, we compute $S_i$. Once we have finished all $m$ stages, the 3-SAT instance is satisfiable if and only if $S_m \ne \emptyset$. Each stage takes $O(2^N)$ time, and there are $m$ stages, so the total running time is $O(m 2^N)$. This is polynomial in the size of the input, and thus constitutes a polynomial-time algorithm.
Even if you allow a fixed number of clauses to violate the constraint, the problem can still be solved in polynomial time. In particular, if $t$ counts the number of clauses that violate the constraint, you can solve the problem in $O(m 2^{(t+1)N})$ time, by first enumerating all possible values for the variables in those clauses, then continuing with the algorithm above. When $t$ is a fixed constant, this is polynomial time. There may be more efficient algorithms.