Lax Lean Archive

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

Descriptive complexity: one-call and subtractive counting reductions

lax-859101·formalized by Pierre Senellart @PierreSenellart · Claude (Anthropic)·created ·GitHub @2c61a96·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 reductions beyond parsimony, from the descriptive-complexity library: one-call and subtractive reductions, and the counting problems that are complete for #P under them but not known to be under parsimonious ones. It builds on the submission on counting problems, #P, and FP (lax-366625) and on the catalog of parsimoniously #P-complete problems lax-280166. These build in turn 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), and AC⁰ (lax-895169).

    A one-call reduction is a relativized first-order interpretation followed by a post-processing term, which computes the count of the source from the answer of the oracle with polynomial terms, powers of two, and the arithmetic of natural numbers: a restricted form of the metric reductions of Krentel, in the statement of Faliszewski and Hemaspaandra. One-call reductions compose, and a parsimoniously #P-complete problem is one-call #P-complete. Since #P is presumably not closed under them, as Toda and Watanabe showed, completeness is for the one-call closure of #P. Subtractive reductions, after Durand, Hermann, and Kolaitis, are chains of strong subtractive and parsimonious steps; #P is closed under them, and a parsimoniously #P-complete problem is #P-complete.

    #DNF is #P-complete under subtractive reductions and one-call #P-complete, although its support is easy: the models of a CNF formula are all the assignments minus the models of the DNF formula of its negation, as Durand, Hermann, and Kolaitis showed and as Durand, Haak, Kontinen, and Vollmer used for #AC⁰. #NAE-SAT, #Set Splitting, #3-Colorability, counting all independent sets and all vertex covers, #2SAT, #HORN-SAT, #Monotone-2SAT, #BIS, and #PP2DNF are one-call #P-complete; the proofs follow the library's tree of reductions, from #SAT and #Independent Set.

    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
    34 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-859101,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: one-call and subtractive counting reductions},
  year = {2026},
  howpublished = {Lax Archive, lax-859101},
  url = {https://laxarchive.org/lax-859101/},
  note = {draft},
}

    References

    1. Pierre Senellart. DescriptiveComplexity: Completeness by First-Order Reductions in Lean. 2026. doi:10.5281/zenodo.21678423 · github.com/PierreSenellart/descriptive-complexity
    2. Mark W. Krentel. The complexity of optimization problems. J. Comput. Syst. Sci. 36(3):490–509, 1988. doi:10.1016/0022-0000(88)90039-6
    3. Piotr Faliszewski and Lane Hemaspaandra. The complexity of power-index comparison. Theor. Comput. Sci. 410(1):101–107, 2009. doi:10.1016/j.tcs.2008.09.034
    4. Seinosuke Toda and Osamu Watanabe. Polynomial-time 1-Turing reductions from #PH to #P. Theor. Comput. Sci. 100(1):205–221, 1992. doi:10.1016/0304-3975(92)90369-Q
    5. Arnaud Durand, Miki Hermann and Phokion G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. Theor. Comput. Sci. 340(3):496–513, 2005. doi:10.1016/j.tcs.2005.03.012
    6. Arnaud Durand, Anselm Haak, Juha Kontinen and Heribert Vollmer. Descriptive Complexity of #AC0^0 Functions. In CSL 2016 62:20:1–20:16, 2016. doi:10.4230/LIPIcs.CSL.2016.20

    Discussion

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

    Loading discussion…