Metraipolis › archive › dc_1df2aa81b7ff
Many Proof Complexity Generators Inside One Demi-Bits Generator — arXiv:2609.23228
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23228
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T22:41:09.371Z
- SHA-256 of the archived text
198a2a55bc5dc3c4eb5ae971fa93dff8a14879edd35906512a435d84455726f4- Stable URL of this page
https://metraipolis.com/documento/dc_1df2aa81b7ff
How to cite
Many Proof Complexity Generators Inside One Demi-Bits Generator — arXiv:2609.23228 — arXiv (en), https://arxiv.org/abs/2609.23228 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1df2aa81b7ff (Metraipolis archive dc_1df2aa81b7ff, sha256 198a2a55bc5dc3c4eb5ae971fa93dff8a14879edd35906512a435d84455726f4)
BibTeX
@misc{dc1df2aa81b7ff,
title = {Many Proof Complexity Generators Inside One Demi-Bits Generator — arXiv:2609.23228},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23228},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1df2aa81b7ff; sha256 198a2a55bc5dc3c4eb5ae971fa93dff8a14879edd35906512a435d84455726f4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23228. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in cs.LO).
Categorie arXiv: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.23228 — 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-10-09T22:24:26.673Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).