{"id":"arxiv/2608.28813","url":"https://arxiv.org/abs/2608.28813","tags":["cs.CC","math.LO"],"score":0,"title":"Unconditional $V^0_1$-independence of a certified hitting-set principle","domain":"cs.CC","source":"arxiv","authors":["Martin Kolář"],"reviews":0,"subject":"cs.CC","summary":"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 $\\mathrm{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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-28","reactions":{}}