# Is retrospective inference NP-hard?

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?

• Sounds a lot like SAT. Have you tried proving it NP-hard? May 19, 2019 at 22:22
• @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/… May 19, 2019 at 23:26