On the Number of Quantifiers Needed to Define Boolean Functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908473595265024 |
|---|---|
| author | Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik |
| author_facet | Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik |
| contents | The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binary strings with an ordering relation, using a technique we call parallel play, which significantly reduces the number of quantifiers needed in many cases. Ordered structures such as strings have historically been notoriously difficult to analyze in the context of these and similar games. Nevertheless, in this paper, we provide essentially tight upper bounds on the number of quantifiers needed to characterize different-sized subsets of strings. The results immediately give bounds on the number of quantifiers necessary to define several different classes of Boolean functions. One of our results is analogous to Lupanov's upper bounds on circuit size and formula size in propositional logic: we show that every Boolean function on $n$-bit inputs can be defined by a FO sentence having $(1 + \varepsilon)n\log(n) + O(1)$ quantifiers, and that this is essentially tight. We reduce this number to $(1 + \varepsilon)\log(n) + O(1)$ when the Boolean function in question is sparse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00688 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Number of Quantifiers Needed to Define Boolean Functions Carmosino, Marco Fagin, Ronald Immerman, Neil Kolaitis, Phokion Lenchner, Jonathan Sengupta, Rik Logic in Computer Science Computational Complexity The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binary strings with an ordering relation, using a technique we call parallel play, which significantly reduces the number of quantifiers needed in many cases. Ordered structures such as strings have historically been notoriously difficult to analyze in the context of these and similar games. Nevertheless, in this paper, we provide essentially tight upper bounds on the number of quantifiers needed to characterize different-sized subsets of strings. The results immediately give bounds on the number of quantifiers necessary to define several different classes of Boolean functions. One of our results is analogous to Lupanov's upper bounds on circuit size and formula size in propositional logic: we show that every Boolean function on $n$-bit inputs can be defined by a FO sentence having $(1 + \varepsilon)n\log(n) + O(1)$ quantifiers, and that this is essentially tight. We reduce this number to $(1 + \varepsilon)\log(n) + O(1)$ when the Boolean function in question is sparse. |
| title | On the Number of Quantifiers Needed to Define Boolean Functions |
| topic | Logic in Computer Science Computational Complexity |
| url | https://arxiv.org/abs/2407.00688 |