CS Paper Radar

Unconditional $V^0_1$-independence of a certified hitting-set principle

Martin Kolář

cs.CC math.LO ·submitted 2026-08-28 19:23 UTC · v1

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 $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 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 $\mathrm{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.

Closest papers

Nearest neighbours by meaning across the whole index.

Coinduction in Grounded Arithmetic

cs.LO math.LOcs.PL ·2026-10-30 ·Bryan Ford
similarity 0.59
Abstract · 75 pages

A grounded arithmetic counts a sentence as true only when a terminating process establishes it; a sentence no such process settles has no value. Such a logic can state that an event happens, but not that it never happens under unbounded choice. This paper extends such a logic so that it can. The base is Reflective Grounded Arithmetic (RGA) with Inductive Grounded Arithmetic (IGA)'s least-fixed-point reading and ground induction. It adds a separate greatest-fixed-point former $ν$ with Park's coinduction rule, proves that one former cannot carry both ground induction and coinduction, and adds a dichotomy rule: the classical disjunction between a least-fixed-point atom and the greatest-fixed-point atom of its dual, under a derivable premise that the body's leaves are decided. The systems are sound for an explicit model reading every $ν$-body at its greatest fixed point, hence consistent; they agree with the least model wherever it has a value and prove sentences it leaves without one. The dichotomy replaces the underivable hypothesis that an order is well-founded by the derivable one that its steps are decided; the change of model pays for the move. With ground induction the dichotomy derives the omniscience rule of the sibling arithmetic OGA, so the system has no semantics whose certificates for universals are its own proofs. The systems prove, as single sentences, that every decided tree is well-founded or has an infinite branch given by a term, total in the new model; that random assignment terminates while its divergent twin runs forever; that a fair loop terminates and the alternating-bit protocol delivers every message; that open games are determined; that the termination gap in Nakata and Uustalu's trace semantics closes; and that Cinderella wins the bucket game at capacity three. Isabelle/HOL checks every result.

0.22

Pointwise provable equality and the failure of composition

cs.LO math.LO ·2026-09-22 ·Florian Lengyel
theorycode/data similarity 0.57
Abstract · 11 pages. Exposition condensed and discussion of related work revised; mathematical statements and proofs unchanged. Clarified the roles of …

In their studies of pathologies in recursion categories, Montagna (1989) and Di Paola--Montagna (1991) introduce the algebraic systems $S'$ and $S'_T$, respectively, and claim that they are categories. We show that the proposed composition is not independent of the choice of representatives. For every consistent recursively enumerable extension $T$ of Peano arithmetic ($\mathrm{PA}$), we exhibit two unary programs whose partial functions are provably equal in $T$, separately at each standard input. Composing each after a program that searches for a $T$-proof of contradiction and returns its code yields programs that are not equivalent in this sense. An alternative proof uses the productivity of the complement of the diagonal halting set. Montagna's $S'$ is the case $T=\mathrm{PA}$. More generally, for consistent $T\supseteq\mathrm{PA}$, pointwise provable equality is a composition congruence exactly when $T$ proves every true $Π^0_1$ sentence, in which case it is extensional equality. This completeness condition fails for every consistent recursively enumerable $T\supseteq\mathrm{PA}$ by Gödel's second incompleteness theorem. For every extension $T\supseteq\mathrm{PA}$, the least composition congruence containing pointwise provable equality is extensional equality if $T$ is $Σ^0_1$-sound and the universal relation otherwise.

0.35

Formalizing PARITY Circuit Lower Bounds in Lean

cs.CC cs.LO ·2026-09-21 ·Saint Wesonga
theorycode/data similarity 0.57
Abstract

We formalize Hastad's PARITY lower bound in Lean using the switching lemma. For every fixed d >= 2, formulas and DAG circuits of computation depth at most d computing PARITY on n inputs require size exp(Omega_d(n^(1/(d-1)))) for all sufficiently large n. This matches the classical upper bound up to constants in the exponent and implies that PARITY is not in nonuniform AC0. We also construct a polynomial-size, logarithmic-depth bounded-fan-in formula family for PARITY, providing a witness to NC1 is not a subset of AC0 for the formalized models. The Lean source code is available at https://github.com/formalcs/circuit-complexity and is checked with Lean 4.33.1 and mathlib 4.33.1.

0.59

Soundness of the GKR Protocol for Sparse-Merkle Updates, with a Machine-Checked Core

cs.CR cs.LO ·2026-10-04 ·Jinwook Kim
theorycode/data similarity 0.56
Abstract · 36 pages, 4 figures, 3 tables. v3: new title; the collision-resistance assumption on the node hash is replaced by a position-binding assumpt…

The GKR soundness theorem bounds the acceptance of a false output claim for a fixed circuit and input. It does not say what the outputs of a compiled circuit mean for that input, and that has to be proved for each family of circuits. For a sparse Merkle tree over a compressing hash, heuristically almost every root admits a valid path for almost any leaf, so the needed statement concerns the witness as well as the claim. We prove per-input soundness for membership, non-membership and update claims, for trees of every depth, in the delegation setting of GKR: the verifier reads the circuit input in the clear and leaves the node hashes to the circuit. Assuming correct hash sub-circuits, every accepted input, honestly encoded or not, determines a valid witness, and the chain constraint cannot be dropped. If the witness read from an input fixed before the challenges is not valid, this verifier accepts with probability at most $\bigl(s_{\mathrm{out}}+\sum_i(8s_i+1)\bigr)/|\mathbb{F}|$ for a circuit with $2^{s_{\mathrm{out}}}$ outputs and $2^{s_i}$ wires read at layer $i$. This covers cube gates for the Poseidon2 S-box and, with $|\mathbb{F}| = p^4$, circuits over the 31-bit KoalaBear field with challenges from its quartic extension. The implemented node hash, a truncated permutation, is not collision resistant, so the statement that accepted runs for one key and root assert the same leaf assumes position binding of the tree. All our results are proved in the paper. Isabelle/HOL also checks a layer-chain bound, the exactness of the verifier's checks on encoded witnesses in a constraint-level model with abstract hash sub-circuits and, over one field, their composition for claims with no valid witness. All bounds concern the interactive public-coin protocol.

0.40

CIC + EM $\vdash$ Con(ZF): the consistency of ZF in type theory with excluded middle and no choice

cs.LO math.LO ·2026-09-19 ·Mario Carneiro
theorycode/data similarity 0.56
Abstract · 13 pages. Lean 4 formalization at https://github.com/digama0/ConZF

The sets-as-trees interpretation of set theory in a dependent type theory with an impredicative universe of propositions validates Zermelo set theory, and it validates Replacement if the type theory has a choice or description operator, which turns a functional relation into a function. It has been natural to expect that without such an operator the strength of the type theory drops well below that of $\mathrm{ZF}$. We show that it does not. In the type theory of Lean with two predicative universes, from excluded middle as the only assumption and with no axiom (no choice, no propositional extensionality, no quotients), we prove the consistency of $\mathrm{ZF}$, stated outright for a first-order proof system. The proof is formalized. The mechanism is the large elimination of the accessibility predicate over a type as large as the type of sets: a recursion on accessibility whose recursive calls are guarded by propositions, and whose later calls are indexed by the value of an earlier call, computes as a term any ordinal that is specified by a proposition through a well-founded tree of a certain shape. We give a rule that produces such a tree for every ordinal, unless some $V_ρ$ is already a model of $\mathrm{ZF}$; the rule does not choose a cofinal map into a limit ordinal but takes all definable ones at once. In the first case the sets-as-trees satisfy Replacement for arbitrary propositional relations. Either way $\mathrm{ZF}$ has a model. Finally, the double negation of excluded middle suffices, and what remains of it is exactly that membership is not not well-founded in the stable reading of sets; this in turn implies the double negation of Markov's principle.

0.46

Automated Theorem Generation in First-Order Logic by Construction from Triangular Standard Contradictions

cs.AI ·2026-10-30 ·Yang Xu, Shuwei Chen, Hailin Guo, Jun Liu
theory similarity 0.56
Abstract · 46 pages, 11 figures

Automated theorem generation (ATG) seeks to construct new theorems rather than merely prove given conjectures. Existing approaches typically generate candidate statements that require subsequent proof or formal verification. We propose a constructive framework for ATG in first-order logic based on triangular standard contradictions. The method constructs minimally unsatisfiable clause sets from selected first-order literals, then forms theorems by retaining some clauses as premises and taking the negation of one clause, or a conjunction of clauses, as the conclusion. Minimal unsatisfiability ensures that the remaining premises are satisfiable, avoiding trivial inference by explosion, while unsatisfiability of the full set guarantees the resulting entailment. Theorems are therefore correct by construction, without a separate proof procedure for each instance. Extending the previously developed $Δ_1$ generator, we introduce seven methods, $Δ_2$--$Δ_8$, forming a unified family of eight theorem-generation methods. Four generators, $Δ_1$--$Δ_4$, have been implemented and released. We also formulate a general $Δ$-class method encompassing the family. Combinatorial analysis demonstrates the capacity to generate large numbers of distinct theorems systematically. This framework offers a principled foundation for automated theorem discovery and the construction of logically guaranteed knowledge.

0.28

On Positive Computation

cs.CC cs.LO ·2026-11-06 ·Eduardo Skapinakis
similarity 0.56
Abstract

We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions). If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$. We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets. Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$.

0.23

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.55
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32