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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Formal Verification of Canonical NAND Circuit Enumeration and Exact 3-CLIQUE Complexity in Lean 4 (CTAV DeepCore, Part 2)

Ivan Antsipau
Zenodo (CERN European Organization for Nuclear Research)
Logic, programming, and type systems
preprint

Formal Verification of Canonical NAND Circuit Enumeration and Exact 3-CLIQUE Complexity in Lean 4 (CTAV DeepCore, Part 2)

Ivan Antsipau
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Logic, programming, and type systems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon