In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard. My question below builds on this to ask whether NP-hardness is recovered when, loosely speaking, there are multiple "layers" of variables leading up to the formula of interest. (This elaboration emerges naturally from a study of spatial Bayesian networks.)


Consider a graph with nodes arranged in rows. The number of nodes doubles in each subsequent row; the graph has one node in the first row, two in the second, four in the third, and so on, for $m$ rows. (There are $n = 2^m - 1$ nodes total in the graph.) Each node takes a state of either 0 or 1 and has up to three "parent" nodes in the subsequent row (when there is such a row). Each parent is "$k$-local": there are fewer than $k$ nodes between the first and last nodes for which it is a parent. ($k$ is a fixed natural number that does not change with $n$.)

For each node $v$, there is a table $T_v$ that lists all possible combinations of states of the parents of $v$ and, for each combination, assigns a state of 0 or 1 to $v$ in a fashion consistent with $v$ being a disjunctive clause of literals of its parents.

Let $(3,k)\text{-SATSTACK}$ denote the decision problem of determining whether there is an assignment of states to the nodes of the graph that assigns state 1 to the first node and is consistent with all $T_v$.

Are there $k$ for which $(3,k)\text{-SATSTACK}$ is NP-hard?


(1) It appears that $(3,k)\text{-SATSTACK}$ is in NP, since we can choose an assignment for each node in the last row, then work backward through the rows, computing the assignment for the rest of the graph in linear time and accepting it if and only if it assigns state 1 to the first node.

(2) It also seems plausible that $(3,k)\text{-SATSTACK}$ is NP-hard, at least for $k$ large enough, since it seems difficult to do better than a procedure in which we work forward from the first row, applying the polynomial-time algorithm noted above to each row and keeping inventory of all satisfying assignments out to that row (which may be an exponentially growing collection).

(3) Nevertheless, it appears challenging to find a polynomial-time reduction showing that $(3,k)\text{-SATSTACK}$ is NP-hard because many of the subsets of $3\text{-SAT}$ (and related problems) that map naturally into $(3,k)\text{-SATSTACK}$ are not NP-complete (see again). So how should we proceed?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.