3
$\begingroup$

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.

enter image description here

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.

all 18 feasible states

Question: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ @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 :) $\endgroup$ – jonem Apr 4 '16 at 21:55
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Apr 4 '16 at 22:00
  • $\begingroup$ @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). $\endgroup$ – jonem Apr 4 '16 at 22:05
  • $\begingroup$ 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)? $\endgroup$ – D.W.♦ Apr 4 '16 at 22:09
  • $\begingroup$ @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? $\endgroup$ – jonem Apr 4 '16 at 22:22
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer! I'm not sure if I fully understand Roth's result, but does this rule out finding decent bounds, too? If not, do you know of any literature that determines such bounds? $\endgroup$ – jonem Apr 4 '16 at 22:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 4 '16 at 22:58
  • $\begingroup$ What is meant by inputs? Are nodes 1 and 2 in the above DAG the inputs? $\endgroup$ – jonem Apr 5 '16 at 0:26
  • $\begingroup$ @rogerG, inputs = leaves $\endgroup$ – D.W.♦ Apr 5 '16 at 4:26

Your Answer

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

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