Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913853969793024 |
|---|---|
| author | Gerbner, Dániel Imolay, András Katona, Gyula O. H. Nagy, Dániel T. Nagy, Kartal Patkós, Balázs Stadler, Domonkos Zólomy, Kristóf |
| author_facet | Gerbner, Dániel Imolay, András Katona, Gyula O. H. Nagy, Dániel T. Nagy, Kartal Patkós, Balázs Stadler, Domonkos Zólomy, Kristóf |
| contents | We study the number of queries needed to identify a monotone Boolean function $f:\{0,1\}^n \rightarrow \{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 $\binom{n}{\lfloor n/2\rfloor}+\binom{n}{\lfloor n/2\rfloor+1}$ 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19833 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem Gerbner, Dániel Imolay, András Katona, Gyula O. H. Nagy, Dániel T. Nagy, Kartal Patkós, Balázs Stadler, Domonkos Zólomy, Kristóf Combinatorics We study the number of queries needed to identify a monotone Boolean function $f:\{0,1\}^n \rightarrow \{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 $\binom{n}{\lfloor n/2\rfloor}+\binom{n}{\lfloor n/2\rfloor+1}$ 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$. |
| title | Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.19833 |