DescriptiveComplexity: Completeness by First-Order Reductions in Lean
Rattachement africain : fr. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
A Lean library for descriptive complexity, built on Mathlib's ModelTheory. Complexity classes are defined logically rather than by a machine model, so membership is a definability witness and hardness a first-order reduction, which is strictly stronger than a polynomial-time (Karp) reduction. The library proves a machine-free Cook-Levin theorem, NP-completeness for all 21 of Karp's problems, completeness results for classes from L to PSPACE and RE, and machine-bridge theorems identifying the logically defined classes with the Turing-machine ones.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
Les institutions déclarées
Une affiliation ne permet pas de déduire la nationalité d’un auteur.