Formal Verification of Canonical NAND Circuit Enumeration and Exact 3-CLIQUE Complexity in Lean 4 (CTAV DeepCore, Part 2)
text This release (Part 2) continues the formalization of syntactic computational complexity in Lean 4.35.0 without external dependencies, building upon Part 1 (DOI: 10.5281/zenodo.24364859). Verified Results (0 sorry): 1. Compile-Time Axiom Firewall: Custom Lean 4 command inspecting the kernel environment for unauthorized axioms. 2. Symmetry-Reduced Canonical Circuit Enumerator: Enforces commutativity on NAND gates to eliminate duplicates and proves completeness/soundness. 3. Exact Two-Sided Calibration for 3-CLIQUE: Establishes Size_NAND(K_3) = 4 using constructive kernel reduction, proving no size-3 circuit computes 3-CLIQUE while providing an explicit 4-gate circuit. Reproducibility and Audit: Verified against standard Lean 4 axioms. Full code, SHA-256 checksums, and verification steps are documented in the release files.
Authors
- Ivan Antsipau
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24377660
- Primary Topic
- Logic, programming, and type systems
- Type
- preprint