Lax Lean Archive

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

Descriptive complexity: a catalog of parsimoniously #P-complete problems

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

    A catalog of parsimoniously #P-complete problems, from the descriptive-complexity library. It builds on the NP core registered as lax-904597, the catalog of NP-complete problems lax-799700, the submission on counting problems, #P, and FP (lax-366625), and the submissions it requires on logarithmic space (lax-485149), polynomial time (lax-535992), and AC⁰ (lax-895169).

    Seventeen counting problems are parsimoniously #P-complete: #3SAT, #1-in-SAT, #Exact Cover, #Knapsack, #0-1 Integer Programming, #Clique, #Independent Set, #Vertex Cover, #Set Packing, #Set Cover, #Hitting Set, #Dominating Set, #Feedback Vertex Set, #Feedback Arc Set, #Steiner Tree, #Directed Hamilton Circuit, and #Hamilton Circuit. Each counts the solutions of a problem of the NP catalog, at exactly the threshold size where the decision problem asks for one at least or at most that large, so that the reductions can be parsimonious. Each is in #P, and its hardness is carried along a parsimonious first-order reduction, ordered or relativized where needed, from a problem proved complete before it; the proofs form the library's tree of reductions rooted at #SAT. The reductions are parsimonious versions of reductions between the decision problems that go back to Karp, and to Schaefer for 1-in-SAT; parsimonious reductions are due to Simon, and the #P-completeness of such counting problems goes back to Valiant. The support of each problem, the instances with a positive count, is the corresponding decision problem, or for four of them implies it.

    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
    56 concepts
    100%
    #Clique is parsimoniously #P-completeThe values of #Clique, #Independent Set,#Vertex CoverCounting cliques, independent sets, andvertex coversCounting dominating setsCounting feedback vertex and arc setsCounting Hamilton circuitsCounting knapsack and 0-1 integerprogramming solutionsCounting the models of 3-CNF and 1-in-CNFformulasCounting exact covers, packings, set covers,and hitting setsCounting Steiner trees#Directed Hamilton Circuit isparsimoniously #P-complete#Dominating Set is parsimoniously#P-completeThe values of #Dominating Set#Exact Cover is parsimoniously#P-complete#Feedback Arc Set is parsimoniously#P-completeThe values of #Feedback Vertex Set,#Feedback Arc Set#Feedback Vertex Set is parsimoniously#P-complete#Hamilton Circuit is parsimoniously#P-completeThe values of #Directed Hamilton Circuit,#Hamilton Circuit#Hitting Set is parsimoniously #P-complete#Independent Set is parsimoniously#P-complete#Knapsack is parsimoniously #P-completeThe values of #Knapsack, #0-1 IntegerProgramming#1-in-SAT is parsimoniously #P-completeThe values of #3SAT, #1-in-SAT#Set Cover is parsimoniously #P-completeThe values of #Exact Cover, #Set Packing,#Set Cover, #Hitting Set#Set Packing is parsimoniously #P-complete#Steiner Tree is parsimoniously#P-completeThe values of #Steiner Tree#3SAT is parsimoniously #P-complete#Vertex Cover is parsimoniously#P-complete#0-1 Integer Programming is parsimoniously#P-completeCounting classesCounting problems and parsimoniousreductions#SAT, counting the models of a CNFformulaThe class #P, by witness countingClique, Independent Set and Vertex CoverClauses, literals and binary numbersDominating SetFeedback Vertex Set and Feedback Arc SetHamilton circuitsKnapsack, in binary1-in-SATProblems given by a property of structuresSet Cover, Hitting Set, Set Packing, ExactCover and Set SplittingSteiner Tree3SAT0-1 integer programmingComplexity classes, cofinal hardness, and NPFirst-order interpretations and first-orderreductionsNondeterministic Turing machines as finitestructuresDecision problems on finite structuresRelativized first-order interpretationsSAT, propositional satisfiabilitySecond-order definability with boundedalternation
    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-280166,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: a catalog of parsimoniously #P-complete problems},
  year = {2026},
  howpublished = {Lax Archive, lax-280166},
  url = {https://laxarchive.org/lax-280166/},
  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. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA 85–103, 1972. doi:10.1007/978-1-4684-2001-2_9
    3. Thomas J. Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA 216–226, 1978. doi:10.1145/800133.804350
    4. 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
    5. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3):410–421, 1979. doi:10.1137/0208032

    Discussion

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

    Loading discussion…