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.

  • 2
    "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. Jul 10 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. – IIAOPSW Jul 10 at 2:40
  • 1
    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 – Martin Schwarz Jul 10 at 7:37
  • 4
    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 Jul 10 at 8:18
  • 1
    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 Jul 10 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.

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.

  • 1
    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) 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 Jul 10 at 6:11

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.