Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > TIM HOFFMANN:
All reports by Author Tim Hoffmann:

TR25-127 | 5th September 2025
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche

Proof Systems That Tightly Characterise Model Counting Algorithms

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 ... more >>>


TR24-030 | 22nd February 2024
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann

Proof Complexity of Propositional Model Counting

Recently, the proof system MICE for the model counting problem #SAT was introduced by Fichte, Hecher and Roland (SAT’22). As demonstrated by Fichte et al., the system MICE can be used for proof logging for state-of-the-art #SAT solvers.
We perform a proof-complexity study of MICE. For this we first simplify ... more >>>




ISSN 1433-8092 | Imprint