Lax Lean Archive

Descriptive complexity: counting problems, #P, and FP

lax-366625·formalized by Pierre Senellart @PierreSenellart · Claude (Anthropic)·registered·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

    Counting problems in descriptive complexity, from the descriptive-complexity library: the classes #P and FP, defined by logics, their closure under parsimonious first-order reductions, and their complete problems. It builds on the NP core registered as lax-904597 and on the submissions on logarithmic space (lax-485149), polynomial time (lax-535992), and AC⁰ (lax-895169).

    A counting problem attaches an isomorphism-invariant natural number to every finite structure, and a parsimonious reduction, after Simon, is a first-order interpretation that preserves it. #P is the class of the numbers of witnesses of existential second-order sentences over ordered structures, after Saluja, Subrahmanyam, and Thakur, and it coincides with the quantitative logic ΣQSO(FO) of Arenas, Muñoz, and Riveros. FP is the class defined by quantitative first-order logic with least fixed points, equivalently by least fixed points holding the binary digits of the number. Both classes are closed under ordered parsimonious reductions, including relativized ones.

    #SAT and the number of accepting runs of a nondeterministic Turing machine are parsimoniously #P-complete, the latter giving #P as the class of the problems reducing to it. The number written by a Boolean circuit, by unit propagation on a Horn formula, and by a deterministic Turing machine are parsimoniously FP-complete. NP is the class of the supports of #P, the support of a parsimoniously #P-hard problem is NP-hard, and the support of a problem of FP is in PTIME; so a parsimoniously #P-hard problem in FP, or one whose support is in PTIME, gives NP ⊆ PTIME.

    The proofs are those of the library's development after version 1.2.2, on its Lean 4.33 branch, 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
    39 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-366625,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: counting problems, #P, and FP},
  year = {2026},
  howpublished = {Lax Archive, lax-366625},
  url = {https://laxarchive.org/lax-366625/},
}

    References

    1. Pierre Senellart. DescriptiveComplexity: Completeness by First-Order Reductions in Lean. 2026. doi:10.5281/zenodo.21678423 · github.com/PierreSenellart/descriptive-complexity
    2. S. Saluja, K. V. Subrahmanyam and M. N. Thakur. Descriptive Complexity of #P Functions. J. Comput. Syst. Sci. 50(3):493–505, 1995. doi:10.1006/jcss.1995.1039
    3. Marcelo Arenas, Martin Muñoz and Cristian Riveros. Descriptive Complexity for Counting Complexity Classes. Log. Methods Comput. Sci. 16(1):9:1–9:42, 2020. doi:10.23638/LMCS-16(1:9)2020
    4. L. G. Valiant. The Complexity of Computing the Permanent. Theor. Comput. Sci. 8(2):189–201, 1979. doi:10.1016/0304-3975(79)90044-6
    5. Stephen A. Cook. The Complexity of Theorem-Proving Procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA 151–158, 1971. doi:10.1145/800157.805047
    6. Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission 9(3):265–266, 1973. Russian original: Problemy Peredachi Informatsii 9(3):115–116.
    7. G. S. Tseitin. On the complexity of derivation in propositional calculus. In Studies in Constructive Mathematics and Mathematical Logic, Part II 115–125, 1968. Translated from the Russian.
    8. Neil Immerman. Descriptive Complexity. Springer, 1999. doi:10.1007/978-1-4612-0539-5
    9. Janos Simon. On the Difference Between One and Many (Preliminary Version). In Automata, Languages and Programming, Fourth Colloquium, ICALP 1977 52:480–491, 1977. doi:10.1007/3-540-08342-1_37

    Discussion

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

    Loading discussion…