# Number of states in an AND-OR DAG

Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND node or an OR node.

Under this setting, I define a notion of a feasible state. A state is a feasible if and only if:

• for every AND node in the true state, all of its parents are in the true state.
• for every OR node in the true state, at least one of its parents are also in the true state.

(Note that a state can still be feasible even if some AND node is false but all of its parents are true.)

As an example, consider the following DAG. Grey nodes are leaf nodes (nodes 1 and 2), orange nodes are OR nodes (node 3), and red nodes are AND nodes (nodes 4,5, and 6). Note that nodes 4 and 5 can be classified as either AND nodes or OR nodes since they only have one parent. There are 18 feasible states of this DAG if I counted right, as seen below. Nodes with a dark interior are true; nodes with a white interior are false. Question: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?

• @D.W. Thanks for the comments. If an OR node is enabled, then it should have at least one parent also enabled. If the OR node is not enabled, then there are no restrictions on its parents (beyond the restrictions imposed by the parents' parents). I hope that makes sense. Also, the blue is rather dark, let's just say filled-in :) Apr 4, 2016 at 21:55
• OK. What kind of answer are you looking for? An algorithm to compute the number, given the DAG as input? Better lower and/or upper bounds? It's not clear what you mean by "the expression for the total number of feasible states" -- there might be no simple mathematical formula, as the number will depend on the particular DAG.
– D.W.
Apr 4, 2016 at 22:00
• @D.W. Ideally, a closed form expression for the total number of feasible states, as a function of the number of leaf nodes and number of each node type with their in-degree, would be nice (I'm not looking for an algorithm). I'm not exactly sure what properties of the DAG this formula would depend on. If a simple formula is not possible then better bounds would be nice (I am thinking that something that includes the $2^\text{max-in-degree}$ would be of some use). Apr 4, 2016 at 22:05
• Have you tried checking whether those parameters are enough to uniquely determine the number of feasible states? That sounds like a lot to hope for -- I'm skeptical. Have you tried searching for a counterexample (two graphs with same in-degree counts, but different number of feasible states)?
– D.W.
Apr 4, 2016 at 22:09
• @D.W. Hmm, I suppose the arguments of the function are part of my question, although something that is pretty difficult to answer :) I'll look for a counterexample. Perhaps a tighter bound is more attainable? Apr 4, 2016 at 22:22

Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no efficient algorithm for solving your problem. In particular, you won't find any closed form.
Roth showed that the number of satisfying assignments is even NP-hard to approximate within $2^{n^{1-\epsilon}}$ for any $\epsilon > 0$. This means that even finding a decent closed-form approximation can be ruled out.
• Depends on your notion of decency. Any bounds you will get will be off by a factor of $2^{n^{1-\epsilon}}$, where $n$ is the number of inputs. Apr 4, 2016 at 22:58