Lax Lean Archive

Descriptive complexity: AC⁰ as a logic

lax-895169·formalized by Pierre Senellart @PierreSenellart · Claude (Anthropic)·registered·created ·GitHub @646a3b4·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    AC⁰ as a logic, from the descriptive-complexity library, built on the NP core registered as lax-904597 and on the classes of logarithmic space and polynomial time, lax-485149 and lax-535992. A decision problem on finite structures is AC⁰ definable when one first-order sentence with the order, addition and multiplication of ranks, FO(≤, +, ×), decides it on every ordered instance, invariantly in the order: the logic that defines the problems of uniform AC⁰, by theorems of Barrington, Immerman and Straubing. No circuit model is introduced.

    The two classical vocabularies define the same problems, FO(≤, +, ×) = FO(≤, +, BIT), where BIT reads a bit of the rank of an element. One direction defines the powers of two from the arithmetic; the other defines multiplication from BIT, through the Bit Sum Lemma, which counts the ones of a word of logarithmic length.

    The machine side is the logarithmic-time hierarchy: a problem is AC⁰ definable exactly when it is decided by an alternating machine with a logarithmic clock and constantly many alternations, which guesses addresses, queries the input at them, and passes over their bits with finite automata.

    AC⁰ definability is closed under complement and contains FO(≤). It is contained in L, by evaluating the sentence with a deterministic multihead automaton, hence in NL; and in PTIME, directly, the numeric predicates being defined by one simultaneous induction, so that every AC⁰ definable problem is definable in FO(LFP) and in FO(≤, IFP).

    The proofs are those of version 1.2.2 of the library, sliced to what these statements use; they assume the submission's own statements where they compose. The library and its documentation are at https://github.com/PierreSenellart/descriptive-complexity and https://pierresenellart.github.io/descriptive-complexity/DescriptiveComplexity.html. The Lean code was written with the assistance of several Claude models; the design and the statements are the author's.

    Concepts

    Concept map
    28 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-895169,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: AC⁰ as a logic},
  year = {2026},
  howpublished = {Lax Archive, lax-895169},
  url = {https://laxarchive.org/lax-895169/},
}

    References

    1. Pierre Senellart and Anton Gnatenko. Descriptive Complexity in Lean: Completeness by First-Order Reductions. 2026. arXiv:2609.18261
    2. Pierre Senellart. DescriptiveComplexity: Completeness by First-Order Reductions in Lean. 2026. doi:10.5281/zenodo.21678423 · github.com/PierreSenellart/descriptive-complexity
    3. David A. Mix Barrington, Neil Immerman and Howard Straubing. On Uniformity within NC1^1. J. Comput. Syst. Sci. 41(3):274–306, 1990. doi:10.1016/0022-0000(90)90022-D
    4. Michael Sipser. Borel Sets and Circuit Complexity. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA 61–69, 1983. doi:10.1145/800061.808733
    5. Walter L. Ruzzo. On Uniform Circuit Complexity. J. Comput. Syst. Sci. 22(3):365–383, 1981. doi:10.1016/0022-0000(81)90038-6
    6. Neil Immerman. Descriptive Complexity. Springer, 1999. doi:10.1007/978-1-4612-0539-5

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…