Generating Models of a Matched Formula With a Polynomial Delay (Extended Abstract)

1 Introduction

In this paper, we consider the problem of counting the models (satisfying assignments) and generating subsets of the models of a given formula in conjunctive normal form (CNF). It is well known that #SAT, the problem of counting the models of a general CNF, is #P-complete. The problem of enumerating the models of a general CNF formula is clearly also hard, because checking whether there is at least one satisfying assignment of the formula, the SAT problem, is NP-complete.

In this paper, we mostly deal with the problem of enumerating models of a formula. This problem is important in areas of research and applications, such as unbounded model checking [Kang and Park, 2005; McMillan, 2002] or data mining [Coquery et al., 2012]. The success of modern SAT solvers inspired design of model counting and enumeration algorithms as well, see e.g. [Jabbour et al., 2014; Morgado and Marques-Silva, 2005]. In addition to the basic enumeration problem in which we do not require the models

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Savick´y and Kuˇcera, 2016].

Petr Kuˇcera

Department of Theoretical Computer Science and Mathematical Logic Faculty of Mathematics and Physics Charles University, Czech Republic kucerap@ktiml.mff.cuni.cz

to be generated in any prescribed order, other versions have been considered, e.g. generating models by non-decreasing weight [Creignou et al., 2011].

Another line of research concentrated on studying special classes of boolean formulas for which an enumeration algorithm with guaranteed complexity could be devised. One can easily find an example of a formula for which the set of models is exponentially larger than the size of the formula itself. In such a case it is reasonable to include the size of the output into the bound on the running time of an enumeration algorithm. More specifically we say that an algorithm which enumerates models of a formula runs in output polynomial time if its running time can be bounded by a polynomial in two variables, the size of the input (i.e. the input formula ϕ) and the size of the output (i.e. the number of models of ϕ). In this paper, we consider more restrictive setting as follows. The algorithm receives as input a formula and generates a sequence of all its models in such a way that the time needed for generating the first model and the time between generating any two consecutive models in the sequence is polynomial in the length of the formula. This type of complexity bound is called a polynomial delay. It should be clear that if we can enumerate models of a formula with a polynomial delay, then we can construct an output polynomial algorithm for this task as well. On the other hand, it can be much harder to get an enumeration algorithm with polynomial delay than an output polynomial algorithm. For an overview of various notions of enumeration complexity see [Johnson et al., 1988].

There are special classes of formulas for which polynomial delay enumeration algorithms have been described, this includes 2-CNF formulas, Horn formulas, generalized satisfiability problems and others, see e.g. [Aceto et al., 2013; Creignou and H´ebrard, 1997; Dechter and Itai, 1992; Kavvadias et al., 2000]. In this paper, we describe another class of formulas for which a polynomial delay enumeration algorithm based on backtrack-free search can be described. On the contrary to such algorithms known for 2-CNF or Horn formulas, the splitting variable in each step cannot be chosen arbitrarily, however, the existence of a suitable variable is guaranteed and it can be efficiently identified.

In particular we consider the class of matched formulas introduced by [Franco and Van Gelder, 2003]. Given a CNF formula ϕ, we consider its incidence graph I(ϕ) defined as follows. I(ϕ) is a bipartite graph with one part consisting of clauses of ϕ and the other part containing the variables of ϕ. An edge {x,C} for a variable x and a clause C is in I(ϕ) if x or x appears in C. It was observed by Aharoni and Linial [1986] and Tovey [1984] that if I(ϕ) admits a matching (i.e. a set of pairwise disjoint edges) of size m (where m is the number of clauses in ϕ), then ϕ is satisfiable. Later the formulas satisfying this condition were called matched formulas by Franco and Van Gelder. Since a matching of maximum size in a bipartite graph can be found in polynomial time, one can check efficiently whether a given formula is matched.

Given a general formula ϕ, we can measure how far it is from being matched by considering its maximum deficiency δ∗ (ϕ), the number of clauses which remain unmatched in a maximum matching of I(ϕ). A formula ϕ is thus matched iff δ∗ (ϕ) = 0. A weaker notion of deficiency δ(ϕ) = m- n, where m is the number of clauses and n the number of the variables in ϕ, is also often being considered.

Matched formulas play a significant role in the theory of satisfiability solving. Since their introduction matched formulas have been considered as a base class in parameterized algorithms for satisfiability, see e.g. the book of [Flum and Grohe, 2006] for an overview of parameterized algorithms theory. In particular, [Fleischner et al., 2002] show that satisfiability of formulas with maximum deficiency bounded by a constant k can be decided in time O(‖ϕ‖nO(k) ) where ‖ϕ‖ is the length of the input formula ϕ and n denotes the number of its variables. This result was later improved by [Szeider, 2003] to an algorithm for satisfiability parameterized with maximum deficiency of a formula with complexity O(2k n3 ). Parameterization based on backdoor sets with respect to matched formulas were considered by Szeider [2007].

Since all matched formulas are trivially satisfiable, we ask a stronger question: How hard is it to count or enumerate the models of a matched formula? We prove that counting the models of a matched formula is a #P-complete problem, and turn our attention to generating models of a matched formula. The main result of the paper is an algorithm which generates models of a matched formula with a polynomial delay. The algorithm starts by constructing a splitting tree whose nodes correspond to either a matched or an unsatisfiable formula. In some cases this strategy is not sufficient since some nodes of the tree cannot be split in this way. We prove that such a node corresponds to a formula which can be satisfied by iterated elimination of pure literals. Formulas with this property will be called pure literal satisfiable. These formulas were studied by [Kullmann, 2000] as a subclass of linearly satisfiable formulas. If a node with a pure literal satisfiable formula is reached, the algorithm switches to a simpler strategy. We prove that the models of a pure literal satisfiable formula can be generated with a delay linear in the length of the formula. On the other hand, the #SAT problem for pure literal satisfiable formulas is #P-complete, because this problem is #P-complete for monotone 2CNFs [Valiant, 1979], which are pure literal satisfiable.

Several generalizations of matched formulas have also been considered in the literature. Kullmann [2000] generalized matched formulas into the class of linearly satisfiable formulas. Autarkies based on matchings were studied by Kullmann [2003]. Szeider [2005] considered another generalization of matched formulas, the classes of biclique satisfiable and var-satisfiable formulas. Unfortunately, for both biclique satisfiable and var-satisfiable formulas it is hard to check if a formula falls into one of these classes.

We show in the paper that the algorithm for efficient generating models of a matched formula does not transfer to the class of linearly satisfiable formulas by demonstrating that it is not possible to generate models of a linearly satisfiable formula with a polynomial delay unless P=NP.

2 Definitions

In this section, we give the necessary definitions and summarize the results we use in the paper.

A Boolean function on n variables is a mapping f : {0, 1}n → {0, 1}. A literal is either a variable (e.g. x), called positive literal, or its negation (e.g. x), called negative literal. A clause is a disjunction of a set of literals, which contains at most one literal for each variable. Formula ϕ is in conjunctive normal form (CNF) or, equivalently, ϕ is a CNF formula, if it is a conjuction of clauses. We shall exclusively work with CNF formulas, in particular by "formula" we always mean a "CNF formula". The size of a formula ϕ is the number of the clauses in ϕ and will be denoted as |ϕ|. The length of a formula ϕ is the total number of occurrences of literals in ϕ, i.e. the sum of the sizes of the clauses in ϕ, and will be denoted as ‖ϕ‖. Given a variable x and a value a ∈ {0, 1}, ϕ[x = a] denotes a formula originating from ϕ by substituting x with value a and the obvious simplifications consisting in removing falsified literals and satisfied clauses. Given a partial assignment x1 = a1, . . . , xk = ak, then ϕ[x1 = a1, . . . , xk = ak] denotes the formula originating from ϕ by substituting the variables according to the specified partial assignment and the obvious simplifications. Similarly, if l1, . . . , lk is a sequence of literals, then ϕ[l1, . . . , lk] denotes the formula obtained from ϕ using the partial assignment defined so that the literals l1, . . . , lk are satisfied. We say that a literal l is pure in a CNF formula, if it occurs in the formula and the negated literal l does not. A literal is irrelevant in a formula, if neither the literal nor its negation occurs in the formula. A variable is pure, if it appears only positively, or only negatively in ϕ, i.e. it appears in a literal which is pure in ϕ.

Let ϕ be a formula defining a Boolean function f on n variables. An assignment of values v ∈ {0, 1}n is a model of ϕ (also a satisfying assignment of ϕ), if it satisfies f, i.e. if f(v) = 1. The set of models of ϕ is denoted as T(ϕ). The models in T(ϕ) are defined on the variables which have an occurrence in ϕ. A partial assignment assigns values only to a subset of the variables.

Note that an empty clause does not admit a satisfying assignment and an empty CNF is satisfied by any assignment.

3 Efficient Splitting Tree Algorithm

The idea of the algorithm is to construct a decision tree for the function represented by a given satisfiable CNF, such that every subtree larger than a single leaf contains a 1-leaf. Consider a decision tree of a function represented by a CNF ϕ.

Each leaf node in this tree labeled with 1 represents a set of models of ϕ, more precisely, a leaf in depth d represents 2n-d models of ϕ. Moreover, different leaves of the tree represent disjoint sets of models. Given a decision tree for the function represented by ϕ, we can, by traversing it, generate all models of ϕ in time proportional to its size. This process leads to a large delay between generating successive models, if the tree contains large subtrees with only 0-leaves. The following condition on a class of formulas describes a situation when this can be avoided.

Definition 3.1. Let U be a class of formulas, let ϕ ∈ U and let x be a variable with an occurrence in ϕ. We say that x is a splitting variable for ϕ relative to U, if for every a ∈ {0, 1}, such that ϕ[x = a] is satisfiable, we have ϕ[x = a] ∈ U. A class of formulas U has the splitting property, if every formula in U containing a variable contains a splitting variable relative to U.

We shall associate a splitting problem with a class of formulas U having splitting property.

Definition 3.2. Let U be a class of formulas with the splitting property. The splitting problem relative to U is the following problem: Given a formula ϕ ∈ U, find a splitting variable for ϕ relative to U and the results of satisfiability tests for the formulas ϕ[x = 0] and ϕ[x = 1].

Note that the complexity of the splitting problem relative to U is also an upper bound on the time of a satisfiability test for formulas in U. This is because a formula ϕ is satisfiable, if and only if for any variable x we have that at least one of the formulas ϕ[x = 0] and ϕ[x = 1] is satisfiable. The result of these satisfiability checks for a splitting variable x is a required part of a solution to the splitting problem.

Theorem 3.3. If a class of formulas U has the splitting property and the splitting problem relative to U can be solved in time c(ϕ), where c(ϕ) ≥ ‖ϕ‖ for each formula ϕ ∈ U, then the models of a formula ϕ ∈ U on n variables can be generated with a delay O(n · c(ϕ)).

Remark 3.4. If ϕcontains a unit clause andU is closed under unit propagation, then a variable x contained in a unit clause is a splitting variable which can be identified efficiently. The reason is that if ϕ is known to be satisfiable and one of the formulas ϕ[x = a] contains an empty clause, then the other is satisfiable.

Remark 3.5. It is not hard to observe that if a class U satisfies that

1. the satisfiability of formulas in U can be tested in polynomial time, and
2. U is closed under partial assignments,

then the splitting problem relative to U has polynomial complexity. All classes of generalized satisfiability problem described by [Creignou and H´ebrard, 1997] have this property. In addition to other classes, consider, for instance, Horn formulas, SLUR formulas, 2CNFs, q-Horn formulas, etc. As a corollary of Theorem 3.3, it is possible to generate the models of formulas in these classes with a polynomial delay.

The main result of this paper is that the splitting problem relative to a slight generalization of matched formulas also has polynomial complexity although the class of matched formulas is not closed under partial assignments.

4 Pure Literal Satisfiable Formulas

Before considering matched formulas, let us look at the class of formulas which are satisfiable by iterated elimination of pure literals which we call pure literal satisfiable.

Definition 4.1. A pure literal sequence for a formula ϕ is a consistent sequence of literals (l1, . . . , lk), such that for every i = 1, . . . , k, the literal li is either pure or irrelevant in the formula ϕ[l1, . . . , li-1].

If L is a pure literal sequence for ϕ, the formula ϕ[L] will be called the reduced formula corresponding to ϕ and L. If ϕ[L] does not contain a pure literal, L will be called a maximal pure literal sequence for ϕ.

Definition 4.2. A formula ϕ is pure literal satisfiable, if there is a pure literal sequence L for ϕ, such that the reduced formula ϕ[L] is empty or, equivalently, the literals in L correspond to a satisfying assignment of ϕ.

A maximal pure literal sequence for a CNF formula can be found in polynomial time by a simple greedy algorithm.

Lemma 4.3. A maximal pure literal sequence L for a CNF formula ϕ can be constructed in time O(‖ϕ‖).

It turns out that ϕ[L] is the same for every maximal pure literal sequence L.

Lemma 4.4. Let ϕ be a CNF formula and let L be a maximal pure literal sequence for ϕ.

1. The formula ϕ[L] is uniquely determined by ϕ.
2. The formula ϕ is pure literal satisfiable, if and only if ϕ[L] is empty.

Let us note that pure literal satisfiable formulas are not closed under partial assignments. Therefore pure literal satisfiable formulas do not satisfy the second property required in Remark 3.5 and we have to put more effort into showing that pure literal satisfiable formulas have the splitting property and that the splitting problem relative to pure literal satisfiable formulas has polynomial complexity.

If we take the literals of a maximal pure literal sequence for a formula ϕ in reversed order, we get the order of variables suitable for selecting a splitting variable. It follows that we can solve the splitting problem for a pure literal satisfiable formula in polynomial time.

Theorem 4.5. The splitting problem relative to pure literal satisfiable formulas can be solved in time O(‖ϕ‖) where ϕ is the input pure literal satisfiable formula. Moreover, the set T (ϕ) of the models of a pure literal satisfiable formula ϕ can be generated with a delay of O(‖ϕ‖).

5 Matched Formulas

In this section we concentrate on matched formulas. In particular we show that the problem of determining the number of models of a matched formula ϕ, i.e. the size |T(ϕ)|, is as hard as a general #SAT problem.

Theorem 5.1. The problem of determining |T(ϕ)| given a matched formula ϕ is #P-complete.

Our goal is to show that we can generate the models of a matched formula with a polynomial delay. Theorem 3.3 cannot be used for this directly, since the class of the matched formulas does not have the splitting property. For example, the monotone formula (x∨y)(x∨z)(y∨z) is matched, but has no splitting variable relative to the class of matched formulas. We thus have to consider a richer class of formulas. The class we consider generalizes matched and pure literal satisfiable formulas as follows.

Definition 5.2. A formula ϕ is called pure literal matched, if ϕ[L] is matched for a maximal pure literal sequence L.

Elimination of a pure literal preserves the property of being matched. Hence, a matched formula is pure literal matched. Clearly, every pure literal satisfiable formula is pure literal matched, since its reduced formula is empty and, hence, matched.

The basic idea of an efficient splitting algorithm for the pure literal matched formulas is presented in the following theorem.

Theorem 5.3. Let ϕ be a matched formula. If for every variable x, which has an occurence in ϕ, there is a ∈ {0, 1}, such that ϕ[x = a] is not matched, then ϕ is pure literal satisfiable.

Assume that ϕ is a pure literal matched formula. If ϕ is actually pure literal satisfiable, then the models of ϕ can be generated with polynomial delay based on Theorem 4.5. Otherwise consider a maximal pure literal sequence L and let ψ = ϕ[L], which is, by the assumption, a matched formula. Since L is maximal, ψ does not contain a pure literal and since ϕ is not pure literal satisfiable, ψ is nonempty. Hence, by Theorem 5.3, there is a variable x of ψ, such that ψ[x = 0] and ψ[x = 1] are both matched. Such x is a splitting variable for ϕ relative to the class of pure literal matched formulas because L can be used as a pure literal sequence for ϕ[x = a] for any value a ∈ {0, 1}. We thus get the following theorem.

Theorem 5.4. The splitting problem relative to pure literal matched formulas can be solved in time O(n · ‖ϕ‖) where ϕ is the input formula on n variables.

Similarly as the class of matched formulas, also the class of pure literal matched formulas is closed under unit propagation and, hence, Remark 3.4 applies to these classes.

As a corollary of Theorem 5.4 and the general bound from Theorem 3.3, we get the main result of the paper.

Corollary 5.5. Models of a pure literal matched formula ϕ, in particular of any matched formula ϕ, on n variables can be generated with a delay O(n2 · ‖ϕ‖).

6 Linearly Satisfiable Formulas

In this section we consider the class of linearly satisfiable formulas. By results of [Kullmann, 2000], this class generalizes both the matched formulas and the pure literal satisfiable formulas and, by combining the proofs, also the class of pure literal matched formulas. In this section, we show that it is not possible to generate models of linearly satisfiable formulas with a polynomial delay unless P=NP.

Theorem 6.1. It is an NP-complete problem to determine, whether a general linearly satisfiable formula has at least 2 models.

Moreover the following is an example of a linearly satisfiable formula which has no splitting variable.

Example 6.2. Denote E = {a ∈ {0, 1}4 | 2 ≤ a1 + a2 + a3 + a4 ≤ 3} and for every Boolean variable x, let x1 = x and x0 = x. The formula

is linearly satisfiable, but has no splitting variable relative to the class of linearly satisfiable formulas.

7 Conclusion and Directions for Further Research

In the paper, we have shown that it is possible to generate the models of a matched formula ϕ on n variables with delay O(n2 · ‖ϕ‖). As a byproduct we have shown that the models of a pure literal satisfiable formula ϕ (i.e. a formula satisfiable by iterated pure literal elimination) can be generated with delay O(‖ϕ‖). We have also shown that this result cannot be generalized for the class of linearly satisfiable formulas since it is not possible to generate models of linearly satisfiable formulas with a polynomial delay unless P=NP.

The algorithms described in the paper for the cases of pure literal satisfiable and pure literal matched formulas can be used in a general algorithm for model enumeration which is based on splitting tree. This, in turn, is any DPLL based enumeration algorithm. To this end, a similar approach to the one described by Stefan Szeider [2003] can be used. Together with a formula ϕ we would keep a maximum matching M of I(ϕ). This maximum matching can then be maintained through the reduction and assignment steps performed in the enumeration algorithm. Once the algorithm arrives at a matched formula, it can select splitting variables in the way we have described in this paper which has a guaranteed polynomial delay.

Recall that Szeider [2003] introduced an algorithm for satisfiability parameterized with maximum deficiency of a formula. This algorithm is based on a DPLL search procedure where between decision steps nontrivial reductions are performed. It would be interesting to know whether the algorithm described by Szeider [2003] could be modified into an algorithm for generating models of a general CNF formula so that the delay is parameterized with maximum deficiency.

Acknowledgments

Petr Savick´y was supported by CE-ITI and GA ˇCR under the grant number GBP202/12/G061 and by the institutional research plan RVO:67985807. Petr Kuˇcera was supported by the Czech Science Foundation (grant GA15-15511S).