Metraipolis › archive › dc_8940f0f4bb22
The CNF Encoding Complexity of Boolean Functions — arXiv:2611.05614
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05614
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:53.814Z
- SHA-256 of the archived text
c15141e66bd222aa31e1a5dc638b601704c01490479fb4330fcdcc11ddbc43e8- Stable URL of this page
https://metraipolis.com/documento/dc_8940f0f4bb22
How to cite
The CNF Encoding Complexity of Boolean Functions — arXiv:2611.05614 — arXiv (en), https://arxiv.org/abs/2611.05614 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8940f0f4bb22 (Metraipolis archive dc_8940f0f4bb22, sha256 c15141e66bd222aa31e1a5dc638b601704c01490479fb4330fcdcc11ddbc43e8)
BibTeX
@misc{dc8940f0f4bb22,
title = {The CNF Encoding Complexity of Boolean Functions — arXiv:2611.05614},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05614},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8940f0f4bb22; sha256 c15141e66bd222aa31e1a5dc638b601704c01490479fb4330fcdcc11ddbc43e8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05614. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each input, then it admits a CNF encoding with $\widetilde{O}(t + \sqrt{mb})$ clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook--Levin theorem, for which a naïve generalization would yield $\widetilde{O}(t+m)$ clauses; our applications leverage $b = o(m)$ to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every $k$-CNF function on $n$ inputs can be encoded with $n^k/2^{\Omega_k(\sqrt{\lg n})}$ clauses. Notably, despite encoding a $k$-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is $\Omega_k(n^{k}/\lg n)$ in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2611.05614 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:19.041Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).