Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

Descriptive complexity: degrees and graph isomorphism

lax-604544·formalized by Pierre Senellart @PierreSenellart · Claude (Anthropic)·created ·GitHub @2c6d7c6·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

    Completeness without a class, from the descriptive-complexity library: the degree of a decision problem under first-order reductions, and the graph isomorphism problems, which are complete for a degree and, conjecturally, for no class defined by a logic. It builds on the NP core registered as lax-904597, the catalog of NP-complete problems lax-799700, and the submissions on logarithmic space (lax-485149), polynomial time (lax-535992), the polynomial hierarchy (lax-564036), and recursive enumerability (lax-624099).

    The degree of a problem is the class of the problems that reduce to it by an ordered first-order reduction, with the hardness of the NP core. A problem is complete for its own degree, completeness for a degree is mutual reducibility, and mutually reducible problems have the same degree. The construction is checked against the classes that have a complete problem: NP is the degree of SAT, coNP of TAUT, PTIME of HORN-SAT, NL of 2SAT, and RE of FINSAT, so that hardness for one of these problems is hardness for its class.

    GI is the degree of Graph Isomorphism, the problem of two simple graphs. It is contained in NP. Digraph Isomorphism and the isomorphism of directed acyclic graphs, given with a witness of acyclicity since acyclicity is not first-order definable, are GI-complete, and GI is also the degree of the directed problem.

    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 and those of the submissions it requires 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
    33 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 submission / another 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-604544,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: degrees and graph isomorphism},
  year = {2026},
  howpublished = {Lax Archive, lax-604544},
  url = {https://laxarchive.org/lax-604544/},
  note = {draft},
}

    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. László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 684–697, 2016. doi:10.1145/2897518.2897542
    4. Johannes Köbler, Uwe Schöning and Jacobo Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, 1993. doi:10.1007/978-1-4612-0333-9
    5. 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…