Unconditional V01-independence of a certified hitting-set principle
Abstract
We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory V01 of AC0-reasoning, unconditionally: V01 proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a V01-provable implication once circuit evaluation is replaced by its certified ΣB0 unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the AC0-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.
Related
- Certified Collision Exclusion and an Unconditional Upper Bound Λ<0.156821 for the de Bruijn--Newman Constant
- A Note on the Finite-Exceedance Dependence Principle for Sum--Maximum Asymptotic Independence
- Distribution of the First Hitting Point on a Boundary Set for a Random Walk in a Lattice Strip
- Hitting Arithmetic Progressions at the Square-Root Scale
- Capacities and Hitting Times for Simple and (critical) Branching Random Walk Sausages
BibTeX
@misc{kolar2026unconditional,
title = {{Unconditional $V^0_1$-independence of a certified hitting-set principle}},
author = {Martin Kolář},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28813},
eprint = {2608.28813},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28813},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Unconditional V^0_1-independence of a certified hitting-set principle
AU - Martin Kolář
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28813
UR - https://arxiv.org/abs/2608.28813
AB - We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of Khaniki, is independent of the two-sorted theory V^0_1 of AC^0-reasoning, unconditionally: V^0_1 proves neither it nor its negation. The same holds for the corresponding certified dual weak pigeonhole principle, whose refutation is witnessed by a single seed that certified-computes every string of the model simultaneously. The mechanism is a bounded-arithmetic transfer of Atserias-Tzameret's reduction from hitting sets to the dual weak pigeonhole principle: the amplification half of that reduction, the sole source of its NP-oracle, is unnecessary at the native stretch of the Nisan-Wigderson map, and the compression half becomes a V^0_1-provable implication once circuit evaluation is replaced by its certified Σ^B_0 unfolding. This is, to our knowledge, the first independence result for a derandomization-flavoured existence principle at the AC^0-reasoning level, and it makes explicit the bridge between the Khaniki Nisan-Wigderson line and the Atserias-Tzameret reverse mathematics of hitting sets.
ER -