Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-127 | 5th September 2025 11:35

Proof Systems That Tightly Characterise Model Counting Algorithms

RSS-Feed




TR25-127
Authors: Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche
Publication: 5th September 2025 11:39
Downloads: 58
Keywords: 


Abstract:

Several proof systems for model counting have been introduced in recent years, mainly in an attempt to model #SAT solving and to allow proof logging of solvers. We reexamine these different approaches and show that: (i) with slight adaptations, the conceptually quite different proof models of the dynamic system MICE and the static system of annotated Decision-DNNFs are equivalent and (ii) they tightly characterise state-of-the-art #SAT solving. Thus, these proof systems provide a precise and robust proof-theoretic underpinning of current model counting. We also propose new strengthenings of these proof systems that might lead to stronger model counters.



ISSN 1433-8092 | Imprint