0
$\begingroup$

Here is a minimal working example of the question:

Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, for $m$ rows. (So $n = m + (m-1)md/2$ nodes total.) Each node takes a state of 0 or 1. All nodes not in row $m$ have $1+d$ "parents" in the next row, and these parents are "local". For example, if $v$ is the $k$th node in row $r < m$, then its parents are nodes $k$ through $k+d$ in row $r+1$.

For each node $v$ in a row $r < m$, 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$.

Let $d\text{-RETROSPECT}$ denote the decision problem of determining whether there is an assignment of states to the nodes of the network that assigns state 1 to the node in the first row and is consistent with all $T_v$.

Are there $d$ for which $d\text{-RETROSPECT}$ is NP-hard?


It seems unlikely that I am the first person to contemplate this. (In fact, in a famous paper in 1990, Cooper showed that if the parents are not required to be local, then the problem is indeed NP-hard for at least $d \geq 2$.) Is a direct proof possible in the local case---e.g., by a polynomial-time reduction from a known NP-complete problem? Or, if not, does anyone know of recent relevant literature?

$\endgroup$
  • $\begingroup$ Sounds a lot like SAT. Have you tried proving it NP-hard? $\endgroup$ – Yuval Filmus May 19 at 22:22
  • $\begingroup$ @Yuval Yes, and indeed Cooper achieves his result by a reduction from 3SAT. The locality constraint is what makes the problem ostensibly more difficult. 3SAT with a similar locality constraint is no longer hard (see [here][1]). Moreover, small examples (e.g., $d = 1$, $n = 6$) indicate that the function that maps the sequence of states in row $m$ to the state of the node in row $1$ cannot be arbitrary as it can in SAT. [1]: cs.stackexchange.com/questions/109357/… $\endgroup$ – SapereAude May 19 at 23:26

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.