<p>A Boolean function <span class="math-container">$\phi$</span> on variables <span class="math-container">$X$</span> is <em><a href="https://en.wikipedia.org/wiki/Evasive_Boolean_function" rel="noreferrer">evasive</a></em> if every decision tree for <span class="math-container">$\phi$</span> has height <span class="math-container">$|X|$</span>. In other words, for any strategy that picks variables of <span class="math-container">$X$</span> 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 <span class="math-container">$X$</span> to know the value to which <span class="math-container">$\phi$</span> evaluates.</p>

<p>A <em>monotone DNF</em> is a disjunction of conjunction of variables, representing a monotone Boolean function on the set <span class="math-container">$X$</span> of variables that it uses.</p>

<p><strong>Which monotone DNFs are evasive?</strong> Is there a characterization of them? What is the complexity, given a monotone DNF, of determining whether it is evasive?</p>

<p>Examples of evasive monotone DNFs include single-clause DNFs, e.g., <span class="math-container">$x \land y \land z$</span>, where we must query the value of every variable (and the adversary can answer <span class="math-container">$1$</span>) until the last one which determines the value of the formula. For another example, take <span class="math-container">$(x \land y) \lor (y \land z)$</span>: if I ask about <span class="math-container">$x$</span> or <span class="math-container">$z$</span> then the opponent answers <span class="math-container">$0$</span> and I'm left with evaluating the other clause, if I ask about <span class="math-container">$y$</span> the opponent answers <span class="math-container">$1$</span> and I must evaluate <span class="math-container">$x \lor z$</span> which requires me to query both variables.</p>

<p>However, not all monotone DNFs are evasive. For instance, for <span class="math-container">$(s \land t) \lor (t \land u) \lor (u \land v)$</span>, I can query variable <span class="math-container">$t$</span>. If it is false, then I know that clauses <span class="math-container">$s\land t$</span> and <span class="math-container">$t \land u$</span> are false, so I can evaluate the function just knowing <span class="math-container">$u$</span> and <span class="math-container">$v$</span> (I don't need to query <span class="math-container">$s$</span>). If it is true, then I have to evaluate <span class="math-container">$s \lor u \lor (u \land v)$</span>, and as the second clause subsumes the third, I just need to know <span class="math-container">$s$</span> and <span class="math-container">$u$</span> (I don't need to query <span class="math-container">$v$</span>).</p>

<p>Playing a bit with the problem in the case of graph DNFs (with two variables per clause), it looks like for a path <span class="math-container">$(x_0 \land x_1) \lor \cdots \lor (x_{n-1} \land x_{n})$</span> with <span class="math-container">$n&gt;0$</span> the function is not evasive iff <span class="math-container">$n$</span> 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.</p>

<p>On graph DNFs, the problem can be seen as a kind of game on the graph of the formula. You pick a vertex <span class="math-container">$v$</span> (= variable) on the graph, and the opponent can choose between:</p>

<ul>
<li>removing <span class="math-container">$v$</span> and all its incident edges (= <span class="math-container">$v$</span> evaluates to <span class="math-container">$0$</span>, all clauses involving it are removed), or</li>
<li>removing the open ball of radius 2 centered on <span class="math-container">$v$</span>, i.e., <span class="math-container">$v$</span>, its adjacent edges, the neighbors of <span class="math-container">$v$</span>, and their adjacent edges (= <span class="math-container">$v$</span> evaluates to <span class="math-container">$1$</span>, all clauses involving <span class="math-container">$v$</span> become singleton clauses involving <span class="math-container">$v$</span>'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).</li>
</ul>

<p>The question is about characterizing and recognizing the graphs <span class="math-container">$G$</span> 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).</p>

CC BY-SA 4.0
2019-07-17T15:42:55.690Z
Possibly relevant references for the lazy: [A survey of evasiveness: Lower bounds on the decision-tree complexity of boolean functions](https://scholar.google.com/scholar?cluster=4534546148343439189&hl=en&as_sdt=1,22), [Lecture Notes on Evasiveness of Graph Properties](https://arxiv.org/abs/cs/0205031)
Neal Young
CC BY-SA 4.0
2019-07-17T20:00:40.323Z
Since the Alexander dual of the corresponding simplicial complex consists of all the independent sets of $G$, a necessary condition for evasiveness is that the independence polynomial of $G$ vanishes at $-1$.
Wei Zhan
<np-hardness><boolean-functions>
Which monotone DNFs are evasive?
Antoine Amarilli 'a3nm'
# Which monotone DNFs are evasive?

(Asked by: username_0 on 2019-07-16)

A Boolean function $\phi$ on variables $X$ is *[evasive](https://en.wikipedia.org/wiki/Evasive_Boolean_function)* 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).

**Tags:** np-hardness, boolean-functions
> **Comments:**
> **username_1**: Possibly relevant references for the lazy: [A survey of evasiveness: Lower bounds on the decision-tree complexity of boolean functions](https://scholar.google.com/scholar?cluster=4534546148343439189&hl=en&as_sdt=1,22), [Lecture Notes on Evasiveness of Graph Properties](https://arxiv.org/abs/cs/0205031)  
> **username_2**: Since the Alexander dual of the corresponding simplicial complex consists of all the independent sets of $G$, a necessary condition for evasiveness is that the independence polynomial of $G$ vanishes at $-1$.  

---

## 0 answers

