Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem

Abstract

We study the number of queries needed to identify a monotone Boolean function $f:\{0,1{\}}^n\to \{0,1\}$. A query consists of a 0-1-sequence, and the answer is the value of $f$ on that sequence. It is well-known that the number of queries needed is $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)+\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor +1}\right)$ in general. Here we study a variant where $f$ has $k$ ``reasons'' to be 1, i.e., its disjunctive normal form has $k$ conjunctions if the redundant conjunctions are deleted. This problem is equivalent to identifying an upfamily in $2^{[n]}$ that has exactly $k$ minimal members. We find the asymptotics on the number of queries needed for fixed $k$. We also study the non-adaptive version of the problem, where the queries are asked at the same time, and determine the exact number of queries for most values of $k$ and $n$.