TL;DR
This paper tackles the challenge of efficiently generating all satisfying assignments (models) for a specific type of logical formula called "matched formulas." The authors introduce a novel algorithm that can generate these models with a "polynomial delay," meaning the time between generating consecutive models is bounded by a polynomial in the formula's size. This is a significant improvement over general methods and has implications for areas like model checking and data mining.
What Problem Does This Paper Address?
Counting and enumerating the models of Boolean formulas, particularly those in Conjunctive Normal Form (CNF), is a fundamental problem in computer science with applications in areas like model checking and data mining. While counting models for general CNF formulas is known to be computationally hard (#P-complete), and enumerating them is also challenging, researchers have explored special classes of formulas for which more efficient algorithms might exist.
This paper focuses on "matched formulas," a class of satisfiable CNF formulas whose incidence graph admits a specific type of matching. The authors first establish that counting the models of even these "simpler" matched formulas remains #P-complete. Their primary goal, however, is to address the generation of these models. The challenge lies in finding an algorithm that doesn't just output all models eventually (output-polynomial time) but does so with a consistent, bounded delay between each model. This "polynomial delay" property is a stronger requirement and is crucial for practical applications where continuous generation of solutions is needed.
Methods
The paper introduces a method based on constructing a "splitting tree" for a given formula. The core idea is to recursively break down the problem by choosing a "splitting variable." For a formula $\phi$ and a variable $x$, the algorithm considers the subformulas $\phi[x=0]$ and $\phi[x=1]$. The key is to find a splitting variable $x$ such that if $\phi$ is satisfiable, then at least one of $\phi[x=0]$ or $\phi[x=1]$ is also satisfiable.
The paper defines a "splitting property" for classes of formulas: a class has this property if every formula within it (that contains a variable) has a splitting variable relative to that class. If a class of formulas has the splitting property and the "splitting problem" (finding a splitting variable and checking satisfiability of the resulting subformulas) can be solved efficiently, then models can be generated with a polynomial delay.
The authors then introduce "pure literal satisfiable formulas" and "pure literal matched formulas" as intermediate classes. They show that pure literal satisfiable formulas can be generated with a delay linear in the formula's size. For pure literal matched formulas, they demonstrate that a splitting variable can be found efficiently, leading to a polynomial delay for generating their models. This approach is then extended to the original class of matched formulas.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- #P-completeness for Matched Formulas: Even for the restricted class of matched formulas, counting the number of models is as hard as the general #SAT problem, highlighting the inherent difficulty of model counting.
- Polynomial Delay is Achievable for Matched Formulas: The paper's main contribution is demonstrating that generating models of matched formulas can be done with a polynomial delay, a significant algorithmic achievement.
- Splitting Trees and Splitting Properties: The concept of a "splitting property" for formula classes is central. If a class possesses this property and the splitting problem is tractable, polynomial delay generation is possible. This provides a general framework for designing such algorithms.
- Pure Literal Satisfiable and Matched Formulas as Building Blocks: The authors leverage these intermediate classes to build up to the result for general matched formulas. Pure literal elimination offers a simpler way to handle certain formula structures.
- Linearly Satisfiable Formulas are Harder: The paper shows that the polynomial delay property does not extend to the broader class of linearly satisfiable formulas, proving that P=NP would be required for such an algorithm. This sets a boundary on the applicability of their techniques.
Key Results
- The problem of counting the models of a matched formula is #P-complete.
- Models of pure literal satisfiable formulas can be generated with a delay of $O(|| \phi ||)$, where $|| \phi ||$ is the size of the formula.
- Models of pure literal matched formulas can be generated with a delay of $O(n \cdot || \phi ||)$, where $n$ is the number of variables.
- Models of matched formulas (and thus pure literal matched formulas) can be generated with a delay of $O(n^2 \cdot || \phi ||)$.
- It is not possible to generate models of linearly satisfiable formulas with a polynomial delay unless P=NP.
Limitations and Future Work
- Linearly Satisfiable Formulas: The paper explicitly states that the polynomial delay algorithm does not transfer to the class of linearly satisfiable formulas, suggesting that achieving polynomial delay for this broader class is likely impossible unless P=NP.
- General CNF Formulas: The results are specific to matched and related classes. Extending polynomial delay generation to arbitrary CNF formulas remains an open and likely intractable problem.
- Future Work: The authors suggest that their splitting tree approach could be integrated into general DPLL-based enumeration algorithms. They also propose exploring whether Szeider's [2003] algorithm for satisfiability parameterized by maximum deficiency could be adapted for model generation with a delay parameterized by deficiency.
Summary updated