Metraipolis › archive › dc_3177e07085cd
Descriptive Complexity in Lean: Completeness by First-Order Reductions — arXiv:2609.18261
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18261
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:11:40.635Z
- SHA-256 of the archived text
020291f34639a3fd5dc6fb1d983c4c4d78e92c23cb269fe2830a5b30a341a805- Stable URL of this page
https://metraipolis.com/documento/dc_3177e07085cd
How to cite
Descriptive Complexity in Lean: Completeness by First-Order Reductions — arXiv:2609.18261 — arXiv (en), https://arxiv.org/abs/2609.18261 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3177e07085cd (Metraipolis archive dc_3177e07085cd, sha256 020291f34639a3fd5dc6fb1d983c4c4d78e92c23cb269fe2830a5b30a341a805)
BibTeX
@misc{dc3177e07085cd,
title = {Descriptive Complexity in Lean: Completeness by First-Order Reductions — arXiv:2609.18261},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18261},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3177e07085cd; sha256 020291f34639a3fd5dc6fb1d983c4c4d78e92c23cb269fe2830a5b30a341a805},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18261. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.LO).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.18261 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:30.217Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).