Counting the Number of Solutions to Constraints
Compared with constraint satisfaction problems, counting problems have received less attention. In this paper, we survey research works on the problems of counting the number of solutions to constraints. The constraints may take various forms, including, formulas in the propositional logic, linear inequalities over the reals or integers, Boolean combination of linear constraints. We describe some techniques and tools for solving the counting problems, as well as some applications (e.g., applications to automated reasoning, program analysis, formal verification and information security).
Code (0)
등록된 구현이 없습니다.
Tasks
SurveySimilar Papers 제목 키워드 기반
Approximate Counting CSP Solutions Using Partition Function
We propose a new approximate method for counting the number of the solutions for constraint satisfaction problem (CSP). The method derives from the partition function based on introducing the free energy and capturing th…
Floating-floating point: a highly accurate number representation with flexible Counting ranges
Efficient number representation is essential for federated learning, natural language processing, and network measurement solutions. Due to timing, area, and power constraints, such applications use narrow bit-width (e.g…
Federated LearningApproximate Integer Solution Counts over Linear Arithmetic Constraints
Counting integer solutions of linear constraints has found interesting applications in various fields. It is equivalent to the problem of counting lattice points inside a polytope. However, state-of-the-art algorithms fo…
Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
Constrained counting and sampling are two fundamental problems in Computer Science with numerous applications, including network reliability, privacy, probabilistic reasoning, and constrained-random verification. In cons…
Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
Designing a search heuristic for constraint programming that is reliable across problem domains has been an important research topic in recent years. This paper concentrates on one family of candidates: counting-based se…
Scheduling