SUPR
Propositional Model Counting
Dnr:

NAISS 2024/5-323

Type:

NAISS Medium Compute

Principal Investigator:

Johannes Klaus Fichte

Affiliation:

Linköpings universitet

Start Date:

2024-07-01

End Date:

2025-07-01

Primary Classification:

10201: Computer Sciences

Secondary Classification:

10105: Computational Mathematics

Tertiary Classification:

10103: Algebra and Logic

Allocation

Abstract

Propositional model counting (MC), also known as number SAT or #SAT, asks to output the number of models of a propositional formula. Despite its computational hardness, the field has seen considerable advances in recent years and highly efficient solvers emerged, capable of solving larger problems each year. These solvers have immediate use in various domains, such as formal verification of hardware, software, and security protocols, combinatorial optimization, computational mathematics, or artificial intelligence in general. Over the last few years, various applications can be witnessed in the literature. Due to the increasing practical interest in counting, the Model Counting Competition (MCC) was conceived in October 2019 and four iterations have successfully carried out. The 5th iteration is planned for 2024 and will be part of the 26th International Conference on Theory and Applications of Satisfiability Testing. The competition identifies new challenging applications and benchmarks, promotes fast and reliable solvers for the problem, and provides a neutral comparison of state-of-the-art solvers. The result of the competition will be a good indicator of the current feasibility of model counting for various applications.