WorksComputer Science
A note on the intractability of enumerating the maximal satisfiable subformulas of a Horn expression
Abstract
We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.
Introduction
A maximal satisfiable subformula (MSS) of a CNF formula is an inclusion-wise maximal subset of its clauses whose conjunction is satisfiable. The MSS enumeration problem asks to list all such subsets without repetition. Since their number may be exponential in the size of the formula at hand, a natural objective is to obtain output-polynomial time algorithms, i.e., algorithms whose running times are polynomial in the combined size of the input and the output. More desirable enumeration algorithms are incremental-polynomial time algorithms that produce the th solution in polynomial time in the input size plus , or polynomial-delay algorithms whose running times before the first output, between consecutive outputs, and after the last output, are bounded by a polynomial in the input size only; see [3, 5] for more details on enumeration problems and complexities.
The problem of enumerating MSS can also be expressed as the enumeration of maximal signatures, where a signature is a binary sequence that records the clauses satisfied by a truth assignment, and maximality is taken bit-wise. Bérczi et al. [1] showed that all signatures of a -CNF can be enumerated in incremental-polynomial time for fixed , and with polynomial delay for tractable CNFs. A family of CNFs is said to be tractable if for any CNF in this family, the satisfiability of any subformula of can be decided in polynomial time even after fixing any subset of the variables at arbitrary values. In the same paper, the authors show that bit-wise minimal signatures of an arbitrary CNF can be listed with polynomial delay, by reducing to maximal independent sets enumeration in graphs, while the maximal ones cannot be enumerated in output polynomial-time unless P = NP, even for 3-CNFs. The latter intractability result follows from the fact that a formula admits a unique maximal signature if and only if the sequence is a signature, i.e., if and only if is satisfiable, and thus relies on the intractability of the satisfiability problem.
The latter observation raises the question of whether the MSS can be enumerated in output-polynomial time for tractable families of CNF formulas. Natural cases include the Horn and 2-CNF formulas. Another natural setting, arising from Schaefer’s dichotomy theorem [4], is that of XOR formulas, whose clauses use the exclusive-or connective and describe parity constraints. Creignou et al. [2] showed that maximal signatures of XOR formulas can be enumerated in incremental-polynomial time, and with polynomial delay if the XOR clauses have size at most 2. In this note, we prove that there is no output-polynomial time algorithm to enumerate maximal satisfiable subformulas of a Horn expression unless P = NP. Thus, the polynomial-time decidability of the satisfiability problem, even after a partial assignment has been fixed, does not suffice for output-polynomial time MSS enumeration. This answers a question that was raised implicitly in [1], explicitly in [2], and at several editions of the Workshop on Enumeration Problems and Applications (WEPA).
Preliminaries
Horn clauses are non-empty disjunctions of literals containing at most one positive literal. Thus, they can consist of a unit clause containing a positive literal , a fully negative clause of unbounded size , or a clause of unbounded size with exactly one positive literal . Clauses of the last type are usually seen as implications and are also denoted as . A Horn expression (also called Horn CNF, or Horn formula) is a conjunction of Horn clauses.
If is a Horn expression with clauses , a maximal satisfiable subformula of is an inclusion-wise maximal set whose conjunction defines a satisfiable Horn formula.
In this note, we consider the following two problems.
Maximal Satisfiable Subformulas of a Horn expression (Horn-MSS·Enum)
Input: a Horn CNF .
Output: the maximal satisfiable subformulas of .
Another solution for Horn-MSS·Enum (Horn-MSS·AnotherSol)
Input: a Horn CNF and a set of its maximal satisfiable subformulas.
Question: is there a maximal satisfiable subformula of that is not in .
Note that given a Horn formula , and since Horn satisfiability is polynomial-time decidable [4], one can greedily compute in polynomial time one of its maximal satisfiable subformulas, by iteratively adding a clause while the obtained set is satisfiable. Moreover, by branching on the clauses that are not part of a solution, one can see that computing constantly many distinct solutions is also tractable. In this note, we however show that computing a next solution, when the number of already obtained solutions is unbounded, is intractable.
The proof
Theorem 3.1. Horn-MSS·AnotherSol is NP-complete.
Proof. The fact that Horn-MSS·AnotherSol is in NP follows from the fact that a maximal satisfiable subformula of that is not in defines a polynomial-size certificate whose validity can be checked in polynomial time.
We prove the NP-hardness by providing a polynomial-time reduction from 3-SAT. Let be an -variable -clause 3-CNF with , and for every , let us fix an arbitrary order on the literals of and denote them by . Let us make the additional assumption that the variables of appear both positively and negatively. Note that this assumption can be made without loss of generality, as variables appearing only positively can be set to true, and those appearing only negatively can be set to false, so that the clauses in which they belong are satisfied, and with no impact on the satisfiability of the remaining part of the formula.
We construct an instance of Horn-MSS·AnotherSol as follows. For every , let where is a variable that represents the occurrence of literal in . Let us point that to distinct ’s and ’s we associate distinct variables even if the corresponding literals coincide. Let , then . Given and , let denote the set of variables in that represent an occurrence of the negation of the literal represented by . We define three families of Horn clauses as follows:
where by for is meant , i.e., the set defines a circular set of implications. Note that and . Let be the Horn expression defined on variable set and consisting of the set of clauses . Then is a -variable -clause Horn expression.
Let us further define:
and put . Note that . This concludes the construction of the instance of Horn-MSS·AnotherSol, whose input validity is argued in the claim below.
Let be the set of maximal satisfiable subformulas of .
Claim 3.2. .
Proof of claim. We first consider , which contains the single set . Note that this set defines a satisfiable subformula, as all its clauses involve at least one positive literal. To see that it is maximal, note that and are contradictory. This proves .
We now consider . Then for some variable . We argue that is satisfiable by describing an assignment. Let a be the assignment that maps all variables of to , except for which is mapped to . Clearly, the clauses in are satisfied. The clause in is also satisfied as it contains . As of the clauses in , they consist in implications having variables for conclusion. Hence all such clauses, except possibly for , are satisfied. Thus a satisfies . Now, note that since consists of unit clauses, any assignment satisfying must actually map the variables of to . Moreover, since , any such assignment must map the remaining variable to . We conclude that there is a unique assignment satisfying , from which we easily see that neither nor can be added to while keeping its satisfiability. We conclude that is maximal, proving .
It remains to consider a set . Then for some pair of variables such that . We argue that is satisfiable by describing an assignment. Let a be the assignment that puts every variable to except for the variables that are mapped to . Note that all the clauses in are satisfied by this assignment. (We note that this set may contain the clauses corresponding to other variables of distinct from but this is not a problem.) Also, the clause in is satisfied. As of the clauses in , they consist in implications having variables for conclusion. All such implications with distinct from and are thus satisfied. As for those having (resp. ) for conclusion, note that they also have (resp. ) in their premise, as part of (resp. ). (In fact, is the only variable of such a premise to be set to by a.) Hence they are also satisfied. Consequently, all implications in are satisfied, and we conclude that a satisfies . Now, note that since consists of unit clauses, any assignment satisfying must map the variables of to . Suppose toward a contradiction that one such assignment satisfying could map one of , say , to . Then, since satisfies and , and since , we would derive that maps to to satisfy the implication, and consequently that maps all variables of to . This contradicts the fact that the clause of belongs to . Hence there is a unique assignment satisfying , from which we derive that cannot be added to while making it satisfiable. So is maximal, proving and concluding the proof. ◇
Claim 3.3. There exists if and only if is satisfiable.
Proof of claim. We first prove the left-to-right implication. Let us assume that there exists . By maximality of and because , we have that .
Let us show that . Suppose toward a contradiction that this is not the case. Then there is a clause of that is not in . By maximality of , because that implication cannot be added while keeping satisfiable, it must be that equals in any truth assignment a satisfying . Hence the clause does not belong to . Since neither nor belong to , we conclude that is a subset of a solution in , a contradiction. We conclude that as desired.
So far, we proved that contains as a subset. We now claim that the remaining set of clauses defines a partial satisfying truth assignment b of that maps each of its variables to if there exists a clause such that , or to otherwise (including the case and ).
Note first that does not contain two clauses , that represent contradicting literals, i.e., such that , as otherwise is a subset of a solution in . Thus, if is part of , then either and is mapped to by b, or and is mapped to by b. So defines a partial truth assignment of . We also deduce that if contains a clause , then .
Moreover, note that whenever contains a clause , since that clause is not part of and is maximal, any assignment a satisfying must map its corresponding variable to . Moreover, since and a satisfies , it must be that at least one element of the premise is mapped to by a. Since , and since these are unit clauses, a must map these variables to . We derive that the elements of the premise mapped to by a belong to . Hence their corresponding clause in belong to . Consequently, under the assumption that contains a clause , it must contain the clauses of corresponding to at least one variable in , at least one variable in , and so on. By the cyclicity of the implications in , must actually contain the clause of at least one variable in each of , showing that b is a satisfying truth assignment of .
We conclude observing that must contain at least one such clause of since contains , and and are contradictory.
We now turn to the right-to-left implication. Let us assume that there exists a satisfying truth assignment b for . We set , and . Then . Consider the truth assignment a which maps every variable to if , and to otherwise, i.e., if . Let us first show that a satisfies .
By construction, the clauses in are satisfied by a. As by assumption contains at least one literal and its negation, the constructed assignment a maps at least one variable to , and so it satisfies as well. So a satisfies . Since b is a satisfying truth assignment of , contains a clause for at least one variable in each of the sets . Hence, a maps to at least one variable in each of the sets . Hence, for every implication , an element of the premise is set to by a. Consequently a satisfies all the implications in , and so a satisfies .
Now, observe that since contains , it is not a subset of a solution in . Since it contains , it is not a subset of a solution in . Finally, since it contains one of every pair of clauses , such that , it is not a subset of a solution in . Consequently, any greedy completion of leads to a maximal satisfiable subformula of which is not in . This completes the proof. ◇
Note that, given an -variable -clause 3-CNF , one may construct in polynomial time in a Horn expression and the sets , and as defined above, all of which of polynomial size in . Claim 3.2 shows that the obtained sets indeed define a valid instance of HORN-MSS.ANOTHER.SOL. Claim 3.3 shows that the existence of an algorithm solving Horn-MSS·AnotherSol in polynomial time provides one deciding the satisfiability of . This concludes the proof.
We derive the following using the folklore observation that the existence of an output-polynomial time algorithm for an enumeration problem yields an (input) polynomial one for deciding whether there exists another solution; see [5].
Corollary 3.4. There is no output-polynomial time algorithm for Horn-MSS·Enum unless .
We finally note that as 3-SAT remains NP-complete when each variable occurs in at most four clauses [6], Theorem 3.1 and Corollary 3.4 even hold for Horn expressions consisting of clauses of size at most 7 plus a single clause of unbounded size.
Acknowledgments. The authors would like to thank Alessio Conte, Alberto L’Episcopo, Kazuhiro Kurita, Arnaud Mary, Giulia Punzi, Takeaki Uno, Simon Vilmin, and Kunihiro Wasa for discussions on this problem and early attempts to obtain output-polynomial time algorithms.
References
- [1][BBČ+21] Kristóf Bérczi, Endre Boros, Ondřej Čepек, Khaled Elbassioni, Petr Kučera, and Kazuhisa Makino. Generating clause sequences of a CNF formula. Theoretical computer science, 856:68–74, 2021.arxiv.org/abs/2002.06727
- [2][CDOV25] Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin. On the Enumeration of Signatures of XOR-CNF’s. In Pat Morin and Eunjin Oh, editors, 19th International Symposium on Algorithms and Data Structures (WADS 2025), volume 349 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.arxiv.org/abs/2402.18537
- [3][JYP88] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988.DOI
- [4][Sch78] Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216–226, 1978.DOI
- [5][Str19] Yann Strozecki. Enumeration complexity. Bulletin of EATCS, 1(129), 2019.
- [6][Tov84] Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete applied mathematics, 8(1):85–89, 1984.DOI