Matching works

3 works

cs.CC — Computational Complexity

Class Numbers of Imaginary Quadratic Orders in the Polynomial Hierarchy

Contributed by Frank Vega

For d≥3d \geq 3 with −d≡0,1(mod4)-d \equiv 0, 1 \pmod 4, let h(−d)h(-d) be the number of classes of primitive positive definite binary quadratic forms of discriminant −d-d. We prove that d↦h(−d)d \mapsto h(-d) is computable in deterministic polynomial time with an oracle for a language in the second level Σ2P\Sigma_2^{\text{P}} of the polynomial hierarchy. The proof uses only reduction theory of binary quadratic forms, Lagrange's theorem and Hermite normal forms; it does not assume the generalized Riemann hypothesis, does not take a generating set of the class group as input, and uses no randomness. A Σ2P\Sigma_2^{\text{P}} oracle finds a generating set of O(log⁡d)O(\log d) forms, and an NP oracle then determines the lattice of relations, whose index is h(−d)h(-d). Consequently, if P=NP\text{P} = \text{NP}, class numbers of imaginary quadratic fields are computable in polynomial time. As an application, the number DnD_n of representations of nn by the ternary form 8x2+2y2+16z28x^2 + 2y^2 + 16z^2 in Tunnell's congruent number criterion equals 2h(−4n)2h(-4n) for square-free n≡2(mod8)n \equiv 2 \pmod 8 and vanishes for square-free n≡6(mod8)n \equiv 6 \pmod 8; hence DnD_n lies in FPΣ2P\text{FP}^{\Sigma_2^{\text{P}}} on even square-free nn, and an exact counting reduction from #SAT\#\text{SAT} to DnD_n would collapse the polynomial hierarchy to Δ3P\Delta_3^{\text{P}}.

Author comments: In this new version, we have added a computer-based numerical verification.

Primarily AI-generated textHuman understanding: all partsHermite normal formTunnell's theorembinary quadratic formsblack-box groupsclass numberscongruent numberscounting complexitypolynomial hierarchy
Nov 04, 20269 pages
PDFView work

cs.CC — Computational Complexity

A Verified Constructive Reduction of the Cook-Levin Theorem in Lean 4: Bridging the Gap Between Complexity Theory and Formal SAT Encodings

Contributed by Jonathan 𝑓(n) Reed

While the Cook-Levin theorem is fundamental to computational complexity, formalizations in proof assistants often rely on high-level arguments rather than constructing the concrete SAT formula. Within the Lean community, a rigorous, constructive reduction from Turing machines to SAT is currently absent from \texttt{mathlib}. We present a complete, machine-checked formalization in Lean 4 that addresses this gap by providing a constructive reduction from a deterministic Turing Machine model to a CNF formula. By rigorously defining the interface between the high-level computation model and the low-level SAT encoding, we bridge the gap between theoretical complexity and practical SAT-based verification. Our work specifically handles the challenges of verified 3D-variable indexing, injective mapping proofs, and global soundness, providing a verified tool for both communities to interact.

A mix of human-written and AI-generated textHuman understanding: all partsConjunctive Normal FormConstructive ReductionCook-Levin TheoremInteractive Theorem ProvingLean 4SAT EncodingsSatisfiability CheckingSymbolic ComputationTuring Machineformal verification
Oct 08, 202616 pages
PDFView work

cs.CC — Computational Complexity

Generalized Bawo: A Finite-State Model and an EXPTIME Upper Bound

Contributed by Isaac kaimfa

Four-row mancala games, including Malawian Bawo and the related East African Bao, have received limited attention in computational complexity theory despite their combinatorial richness. This paper introduces GENERALIZED-BAWO-WIN, a finite-state two-player game model inspired by Malawian Bawo. The model is parameterized by a half-board width n and a binary-encoded lap cap L, and incorporates relay sowing, marker-pit capture, a formalized capture-relay rule (abstracting kichwa), mandatory capture, a singleton-start prohibition, and an explicit lap-cap truncation rule that guarantees move termination. We prove that GENERALIZED-BAWO-WIN belongs to EXPTIME under these semantics. The proof proceeds by establishing that the game's state space has size at most 2poly(|I|), that legal successors can be generated in 2poly(|I|) time, and that a WIN/LOSS/DRAW retrograde attractor can be computed over the resulting finite game graph. We emphasize that this is an upper bound: no hardness result is established. We further emphasize that the theorem applies only to the formally defined generalized model and does not classify Bao as played in East Africa, whose rules differ materially.

A mix of human-written and AI-generated textHuman understanding: all partsEXPTIMEcombinatorial gamescomputational complexityfinite gamesgeneralized Bawostate-space complexity
Sep 28, 202612 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations