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).


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.