Identification of a monotone Boolean function with k “reasons” as a combinatorial search problem
Dániel Gerbner, András Imolay, Gyula O. H. Katona, Dániel T. Nagy, Kartal Nagy, Balázs Patkós, Domonkos Stadler, Kristóf Zólomy · Discrete Applied Mathematics · 2025
We study the number of queries needed to identify a monotone Boolean function . A query consists of a 0-1-sequence, and the answer is the value of on that sequence. It is well-known that the number of queries needed is in general. Here we study a variant where has “reasons” to be 1, i.e., its disjunctive normal form has conjunctions if the redundant conjunctions are deleted. This problem is equivalent to identifying an upfamily in that has exactly minimal members. We find the asymptotics on the number of queries needed for fixed . 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 and .