<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-07-10T02:08:40.133Z
2018-07-10T02:08:40.133Z
D.W.
<p>Incident graph of a SAT formula is a bipartite graph that has a vertex for each clause and each variable. We add edges between a clause and all of its variables. If the incident graph has bounded treewidth then we can decide the SAT formula in P, actually we can do much more. Your incident graph is very restricted. E.g it is a bounded pathwidth graph, so it is polynomial time solvable. For the above well known structural result e.g. take a look at: <a href="https://www.sciencedirect.com/science/article/pii/S0166218X07004106" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S0166218X07004106</a>.</p>

CC BY-SA 4.0
2018-07-10T06:11:06.400Z
Actually, even the primal graph (one edge between two vertices if they appears in the same clause) has bounded pathwidth in this case. See also [(1)](https://www.ac.tuwien.ac.at/files/pub/SamerSzeider10.pdf) that may be more accessible or @D.W. answer which is roughly the same idea as these algorithms. (1) *Algorithms for propositional model counting*, Marko Samer, Stefan Szeider, J. Discrete Algorithms, volume 8, number 1, pages 50-64, 2010.
holf
CC BY-SA 4.0
2018-07-10T03:45:05.847Z
2018-07-10T05:40:30.403Z
2018-07-10T05:40:30.403Z
Saeed
<p>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.</p>

<p>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$. </p>

<p>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.  </p>

<p>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? </p>

<p>By hard I mean a heuristic solver would fall back on the worst case. </p>

CC BY-SA 4.0
2018-07-10T01:57:36.680Z
"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.
CC BY-SA 4.0
2018-07-10T02:40:59.463Z
"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.
IIAOPSW
CC BY-SA 4.0
2018-07-10T07:37:51.080Z
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 https://arxiv.org/abs/1312.1469
For qubits the problem is QMA-complete in 2D. https://arxiv.org/abs/quant-ph/0504050
Martin Schwarz
CC BY-SA 4.0
2018-07-10T08:18:25.543Z
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.
IIAOPSW
CC BY-SA 4.0
2018-07-10T08:26:53.363Z
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.
Martin Schwarz
CC BY-SA 4.0
2018-07-11T09:18:38.163Z
Since you're a physicist you might be interested in looking at Cheeseman et al's paper [Where the *Really* Hard Problems Are](https://ijcai.org/Proceedings/91-1/Papers/052.pdf). I've heard that the jury is still somewhat out on the idea, but it proposes a connection between hard instances of problems and phase transitions. It feels to me that the lack of hard instances of 3-SAT on a 1D line might have to do with the impossibility of phase transitions in one dimensional spin systems. Or maybe not. But it's a fun thing to think about.
N. Virgo
<np-hardness><sat>
Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?
IIAOPSW
# Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

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

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.

**Tags:** np-hardness, sat
> **Comments:**
> **username_1**: "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?  
> **username_0**: "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.  
> **username_2**: 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 https://arxiv.org/abs/1312.1469 For qubits the problem is QMA-complete in 2D. https://arxiv.org/abs/quant-ph/0504050  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: Since you're a physicist you might be interested in looking at Cheeseman et al's paper [Where the *Really* Hard Problems Are](https://ijcai.org/Proceedings/91-1/Papers/052.pdf). I've heard that the jury is still somewhat out on the idea, but it proposes a connection between hard instances of problems and phase transitions. It feels to me that the lack of hard instances of 3-SAT on a 1D line might have to do with the impossibility of phase transitions in one dimensional spin systems. Or maybe not. But it's a fun thing to think about.  

---

## 2 answers

### Answer by username_1 on 2018-07-10. Score: 31

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.


---

### Answer by username_4 on 2018-07-10. Score: 17

Incident graph of a SAT formula is a bipartite graph that has a vertex for each clause and each variable. We add edges between a clause and all of its variables. If the incident graph has bounded treewidth then we can decide the SAT formula in P, actually we can do much more. Your incident graph is very restricted. E.g it is a bounded pathwidth graph, so it is polynomial time solvable. For the above well known structural result e.g. take a look at: <https://www.sciencedirect.com/science/article/pii/S0166218X07004106>.

> **Comments:**
> **username_5**: Actually, even the primal graph (one edge between two vertices if they appears in the same clause) has bounded pathwidth in this case. See also [(1)](https://www.ac.tuwien.ac.at/files/pub/SamerSzeider10.pdf) that may be more accessible or @D.W. answer which is roughly the same idea as these algorithms. (1) *Algorithms for propositional model counting*, Marko Samer, Stefan Szeider, J. Discrete Algorithms, volume 8, number 1, pages 50-64, 2010.  

---

