A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an adversary can answer the queries such that the strategy needs to ask about the value of all variables of $X$ to know the value to which $\phi$ evaluates.
A monotone DNF is a disjunction of conjunction of variables, representing a monotone Boolean function on the set $X$ of variables that it uses.
Which monotone DNFs are evasive? Is there a characterization of them? What is the complexity, given a monotone DNF, of determining whether it is evasive?
Examples of evasive monotone DNFs include single-clause DNFs, e.g., $x \land y \land z$, where we must query the value of every variable (and the adversary can answer $1$) until the last one which determines the value of the formula. For another example, take $(x \land y) \lor (y \land z)$: if I ask about $x$ or $z$ then the opponent answers $0$ and I'm left with evaluating the other clause, if I ask about $y$ the opponent answers $1$ and I must evaluate $x \lor z$ which requires me to query both variables.
However, not all monotone DNFs are evasive. For instance, for $(s \land t) \lor (t \land u) \lor (u \land v)$, I can query variable $t$. If it is false, then I know that clauses $s\land t$ and $t \land u$ are false, so I can evaluate the function just knowing $u$ and $v$ (I don't need to query $s$). If it is true, then I have to evaluate $s \lor u \lor (u \land v)$, and as the second clause subsumes the third, I just need to know $s$ and $u$ (I don't need to query $v$).
Playing a bit with the problem in the case of graph DNFs (with two variables per clause), it looks like for a path $(x_0 \land x_1) \lor \cdots \lor (x_{n-1} \land x_{n})$ with $n>0$ the function is not evasive iff $n$ is a multiple of 3, and this seems to generalize to trees if there is some kind of tree structure on nodes that are 3 steps apart. For general graphs, I have no idea. I have looked for related work about evasiveness and decision tree complexity for monotone CNFs and DNFs but I didn't find anything relevant.
On graph DNFs, the problem can be seen as a kind of game on the graph of the formula. You pick a vertex $v$ (= variable) on the graph, and the opponent can choose between:
- removing $v$ and all its incident edges (= $v$ evaluates to $0$, all clauses involving it are removed), or
- removing the open ball of radius 2 centered on $v$, i.e., $v$, its adjacent edges, the neighbors of $v$, and their adjacent edges (= $v$ evaluates to $1$, all clauses involving $v$ become singleton clauses involving $v$'s neighbors, you will need to ask about each of these neighbors because each has a singleton clause involving it, but these singleton clauses subsume all other clauses involving the neighbors so you get to remove them).
The question is about characterizing and recognizing the graphs $G$ for which you have a strategy that guarantees that you win, where "winning" means "reaching a graph with an isolated vertex" (= a variable that you do not need to ask about).
