betaFeedback

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 ϕ\phi 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 iith solution in polynomial time in the input size plus ii, 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 kk-CNF can be enumerated in incremental-polynomial time for fixed kk, and with polynomial delay for tractable CNFs. A family of CNFs is said to be tractable if for any CNF ϕ\phi in this family, the satisfiability of any subformula of ϕ\phi 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 ϕ\phi admits a unique maximal signature if and only if the sequence (1,…,1)(1,\ldots,1) is a signature, i.e., if and only if ϕ\phi 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 (x)(x), a fully negative clause of unbounded size (x‾1∨⋯∨x‾k)(\overline{x}_1 \lor\cdots\lor\overline{x}_k), or a clause of unbounded size with exactly one positive literal (x‾1∨⋯∨x‾k∨y)(\overline{x}_1 \lor\cdots\lor\overline{x}_k \lor y). Clauses of the last type are usually seen as implications and are also denoted as {x1,…,xk}→y\{x_1,\ldots,x_k\} \to y. A Horn expression (also called Horn CNF, or Horn formula) is a conjunction of Horn clauses.

If ϕ\phi is a Horn expression with clauses C1,…,CmC_1,\ldots,C_m, a maximal satisfiable subformula of ϕ\phi is an inclusion-wise maximal set S⊆{C1,…,Cm}S \subseteq\{C_1,\ldots,C_m\} whose conjunction ⋀S\bigwedge S 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 ϕ\phi.

Output: the maximal satisfiable subformulas of ϕ\phi.

Another solution for Horn-MSS·Enum (Horn-MSS·AnotherSol)

Input: a Horn CNF ϕ\phi and a set SS of its maximal satisfiable subformulas.

Question: is there a maximal satisfiable subformula of ϕ\phi that is not in SS.

Note that given a Horn formula ϕ\phi, 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 φ\varphi that is not in S\mathcal{S} 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 ψ=⋀j=1mCj\psi= \bigwedge_{j=1}^{m} C_j be an nn-variable mm-clause 3-CNF with n,m≥2n,m \ge2, and for every j∈[m]j \in[m], let us fix an arbitrary order on the literals of CjC_j and denote them by ℓj,1,ℓj,2,ℓj,3\ell_{j,1},\ell_{j,2},\ell_{j,3}. Let us make the additional assumption that the variables of ψ\psi 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 j∈[m]j \in[m], let Vj:={vj,1,vj,2,vj,3}V_j := \{v_{j,1},v_{j,2},v_{j,3}\} where vj,iv_{j,i} is a variable that represents the occurrence of literal ℓj,i\ell_{j,i} in CjC_j. Let us point that to distinct ii’s and jj’s we associate distinct variables vj,iv_{j,i} even if the corresponding literals coincide. Let V:=⋃j=1mVjV := \bigcup_{j=1}^{m} V_j, then ∣V∣=3m|V| = 3m. Given j∈[m]j \in[m] and i∈[3]i \in[3], let Lj,i:={vj,i′:ℓj,i′=ℓj,i‾}L_{j,i} := \{v_{j,i'} : \ell_{j,i'} = \overline{\ell_{j,i}}\} denote the set of variables in VV that represent an occurrence of the negation of the literal represented by vj,iv_{j,i}. We define three families of Horn clauses as follows:

A:={(vj,i):j∈[m], i∈[3]},A := \{(v_{j,i}) : j \in[m],\ i \in[3]\},
B:={⋁j∈[m]i∈[3]vj,i‾},B := \left\{\bigvee_{\substack{j \in[m]\\ i \in[3]}} \overline{v_{j,i}}\right\},
C:={Lj,i∪Vj−1→vj,i:j∈[m], i∈[3]}.C := \{L_{j,i} \cup V_{j-1} \to v_{j,i} : j \in[m],\ i \in[3]\}.

where by Vj−1V_{j-1} for j=1j = 1 is meant VmV_m, i.e., the set CC defines a circular set of implications. Note that ∣A∣=∣C∣=3m|A| = |C| = 3m and ∣B∣=1|B| = 1. Let φ\varphi be the Horn expression defined on variable set VV and consisting of the set of clauses A∪B∪CA \cup B \cup C. Then φ\varphi is a 3m3m-variable 6m+16m+1-clause Horn expression.

Let us further define:

S1:={A∪C},\mathcal{S}_1 := \{A \cup C\},
S2:={(A∪B∪C)∖{(vj,i), Lj,i∪Vj−1→vj,i}:j∈[m], i∈[3]},\mathcal{S}_2 := \{(A \cup B \cup C) \setminus\{(v_{j,i}),\ L_{j,i} \cup V_{j-1} \to v_{j,i}\} : j \in[m],\ i \in[3]\},
S3:={(A∪B∪C)∖{(vj,i),(vj,i′)}:j∈[m], i∈[3] and vj,i′∈Lj,i}.\mathcal{S}_3 := \{(A \cup B \cup C) \setminus\{(v_{j,i}),(v_{j,i'})\} : j \in[m],\ i \in[3]\text{ and }v_{j,i'} \in L_{j,i}\}.

and put S:=S1∪S2∪S3\mathcal{S} := \mathcal{S}_1 \cup\mathcal{S}_2 \cup\mathcal{S}_3. Note that ∣S∣=O(n+m2)|\mathcal{S}| = O(n+m^2). This concludes the construction of the instance of Horn-MSS·AnotherSol, whose input validity is argued in the claim below.

Let S∗\mathcal{S}^* be the set of maximal satisfiable subformulas of φ\varphi.

Claim 3.2. S1∪S2∪S3⊆S∗\mathcal{S}_1 \cup\mathcal{S}_2 \cup\mathcal{S}_3 \subseteq\mathcal{S}^*.

Proof of claim. We first consider S1\mathcal{S}_1, which contains the single set A∪CA \cup C. 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 A‾\overline{A} and BB are contradictory. This proves S1⊆S∗\mathcal{S}_1 \subseteq\mathcal{S}^*.

We now consider S∈S2S \in\mathcal{S}_2. Then S=(A∖{(vj,i)})∪B∪(C∖{Lj,i∪Vj−1→vj,i})S = (A \setminus\{(v_{j,i})\}) \cup B \cup(C \setminus\{L_{j,i} \cup V_{j-1} \to v_{j,i}\}) for some variable vj,iv_{j,i}. We argue that SS is satisfiable by describing an assignment. Let a be the assignment that maps all variables of VV to 11, except for vj,iv_{j,i} which is mapped to 00. Clearly, the clauses in A∖{(vj,i)}A \setminus\{(v_{j,i})\} are satisfied. The clause in BB is also satisfied as it contains v‾j,i\overline{v}_{j,i}. As of the clauses in CC, they consist in implications having variables vj′,i′v_{j',i'} for conclusion. Hence all such clauses, except possibly for Lj,i∪Vj−1→vj,iL_{j,i} \cup V_{j-1} \to v_{j,i}, are satisfied. Thus a satisfies SS. Now, note that since A∖{(vj,i)}A \setminus\{(v_{j,i})\} consists of unit clauses, any assignment a′\mathbf{a}' satisfying SS must actually map the variables of V∖{vj,i}V \setminus\{v_{j,i}\} to 11. Moreover, since B⊆SB \subseteq S, any such assignment a′\mathbf{a}' must map the remaining variable vj,iv_{j,i} to 00. We conclude that there is a unique assignment a′=a\mathbf{a}' = \mathbf{a} satisfying SS, from which we easily see that neither (vj,i)(v_{j,i}) nor Lj,i∪Vj−1→vj,iL_{j,i} \cup V_{j-1} \to v_{j,i} can be added to SS while keeping its satisfiability. We conclude that SS is maximal, proving S2⊆S∗\mathcal{S}_2 \subseteq\mathcal{S}^*.

It remains to consider a set S∈S3S \in\mathcal{S}_3. Then S=(A∖{(vj,i),(vj′,i′)})∪B∪CS = (A \setminus\{(v_{j,i}), (v_{j',i'})\}) \cup B \cup C for some pair of variables vj,i,vj′,i′v_{j,i}, v_{j',i'} such that vj′,i′∈Lj,iv_{j',i'} \in L_{j,i}. We argue that SS is satisfiable by describing an assignment. Let a be the assignment that puts every variable to 11 except for the variables vj,i,vj′,i′v_{j,i}, v_{j',i'} that are mapped to 00. Note that all the clauses in A∖{(vj,i),(vj′,i′)}A \setminus\{(v_{j,i}), (v_{j',i'})\} are satisfied by this assignment. (We note that this set may contain the clauses corresponding to other variables vj′′,i′′v_{j'',i''} of Lj,iL_{j,i} distinct from vj′,i′v_{j',i'} but this is not a problem.) Also, the clause in BB is satisfied. As of the clauses in CC, they consist in implications having variables vj′′,i′′v_{j'',i''} for conclusion. All such implications with vj′′,i′′v_{j'',i''} distinct from vj,iv_{j,i} and vj′,i′v_{j',i'} are thus satisfied. As for those having vj,iv_{j,i} (resp. vj′,i′v_{j',i'}) for conclusion, note that they also have vj′,i′v_{j',i'} (resp. vj,iv_{j,i}) in their premise, as part of Lj,iL_{j,i} (resp. Lj′,i′L_{j',i'}). (In fact, vj′,i′v_{j',i'} is the only variable of such a premise to be set to 00 by a.) Hence they are also satisfied. Consequently, all implications in CC are satisfied, and we conclude that a satisfies SS. Now, note that since A∖{(vj,i),(vj′,i′)}A \setminus\{(v_{j,i}), (v_{j',i'})\} consists of unit clauses, any assignment a′\mathbf{a}' satisfying SS must map the variables of V∖{vj,i,vj′,i′}V \setminus\{v_{j,i},v_{j',i'}\} to 11. Suppose toward a contradiction that one such assignment a′\mathbf{a}' satisfying SS could map one of vj,i,vj′,i′v_{j,i},v_{j',i'}, say vj′,i′v_{j',i'}, to 11. Then, since a′\mathbf{a}' satisfies SS and Lj,i∪Vj−1→vj,i∈SL_{j,i} \cup V_{j-1} \to v_{j,i} \in S, and since Lj,i∪Vj−1⊆a′−1(1)L_{j,i} \cup V_{j-1} \subseteq\mathbf{a}'^{-1}(1), we would derive that a′\mathbf{a}' maps vj,iv_{j,i} to 11 to satisfy the implication, and consequently that a′\mathbf{a}' maps all variables of VV to 11. This contradicts the fact that the clause of BB belongs to SS. Hence there is a unique assignment a′=a\mathbf{a}' = \mathbf{a} satisfying SS, from which we derive that (vj,i),(vj′,i′)(v_{j,i}), (v_{j',i'}) cannot be added to SS while making it satisfiable. So SS is maximal, proving S3⊆S∗\mathcal{S}_3 \subseteq\mathcal{S}^* and concluding the proof. ◇

Claim 3.3. There exists S∈S∗∖(S1∪S2∪S3)S \in\mathcal{S}^* \setminus(\mathcal{S}_1 \cup\mathcal{S}_2 \cup\mathcal{S}_3) if and only if ψ\psi is satisfiable.

Proof of claim. We first prove the left-to-right implication. Let us assume that there exists S∈S∗∖(S1∪S2∪S3)S \in\mathcal{S}^* \setminus(\mathcal{S}_1 \cup\mathcal{S}_2 \cup\mathcal{S}_3). By maximality of SS and because S∉S1S \notin\mathcal{S}_1, we have that B⊆SB \subseteq S.

Let us show that C⊆SC \subseteq S. Suppose toward a contradiction that this is not the case. Then there is a clause Lj,i∪Vj−1→vj,iL_{j,i} \cup V_{j-1} \to v_{j,i} of CC that is not in SS. By maximality of SS, because that implication cannot be added while keeping SS satisfiable, it must be that vj,iv_{j,i} equals 00 in any truth assignment a satisfying SS. Hence the clause (vj,i)∈A(v_{j,i}) \in A does not belong to SS. Since neither (vj,i)(v_{j,i}) nor Lj,i∪Vj−1→vj,iL_{j,i} \cup V_{j-1} \to v_{j,i} belong to SS, we conclude that SS is a subset of a solution in S2S_2, a contradiction. We conclude that C⊆SC \subseteq S as desired.

So far, we proved that SS contains B∪CB \cup C as a subset. We now claim that the remaining set of clauses I:=A∖SI := A \setminus S defines a partial satisfying truth assignment b of ψ\psi that maps each of its variables xx to 11 if there exists a clause (vj,i)∈I(v_{j,i}) \in I such that ℓj,i=x\ell_{j,i} = x, or to 00 otherwise (including the case (vj,i)∈I(v_{j,i}) \in I and ℓj,i=x‾\ell_{j,i} = \overline{x}).

Note first that II does not contain two clauses (vj,i)(v_{j,i}), (vj′,i′)(v_{j',i'}) that represent contradicting literals, i.e., such that vj′,i′∈Lj,iv_{j',i'} \in L_{j,i}, as otherwise SS is a subset of a solution in S3S_3. Thus, if (vj,i)(v_{j,i}) is part of II, then either ℓj,i=x\ell_{j,i} = x and xx is mapped to 11 by b, or ℓj,i=x‾\ell_{j,i} = \overline{x} and xx is mapped to 00 by b. So II defines a partial truth assignment of ψ\psi. We also deduce that if II contains a clause (vj,i)(v_{j,i}), then {(vj′,i′):vj′,i′∈Lj,i}⊆S\{(v_{j',i'}) : v_{j',i'} \in L_{j,i}\} \subseteq S.

Moreover, note that whenever II contains a clause (vj,i)(v_{j,i}), since that clause is not part of SS and SS is maximal, any assignment a satisfying SS must map its corresponding variable vj,iv_{j,i} to 00. Moreover, since Lj,i∪Vj−1→vj,i∈SL_{j,i} \cup V_{j-1} \to v_{j,i} \in S and a satisfies SS, it must be that at least one element of the premise Lj,i∪Vj−1L_{j,i} \cup V_{j-1} is mapped to 00 by a. Since {(vj′,i′):vj′,i′∈Lj,i}⊆S\{(v_{j',i'}) : v_{j',i'} \in L_{j,i}\} \subseteq S, and since these are unit clauses, a must map these variables vj′,i′v_{j',i'} to 11. We derive that the elements of the premise mapped to 00 by a belong to Vj−1V_{j-1}. Hence their corresponding clause in AA belong to II. Consequently, under the assumption that II contains a clause (vj,i)(v_{j,i}), it must contain the clauses of AA corresponding to at least one variable in Vj−1V_{j-1}, at least one variable in Vj−2V_{j-2}, and so on. By the cyclicity of the implications in CC, II must actually contain the clause of at least one variable in each of V1,…,VmV_1,\ldots,V_m, showing that b is a satisfying truth assignment of ψ\psi.

We conclude observing that II must contain at least one such clause of AA since SS contains BB, and ⋀A\bigwedge A and BB are contradictory.

We now turn to the right-to-left implication. Let us assume that there exists a satisfying truth assignment b for ψ\psi. We set I:={(vj,i):ℓj,i is satisfied by **b**}I := \{(v_{j,i}) : \ell_{j,i}\text{ is satisfied by **b**}\}, and S=(A∪B∪C)∖IS = (A \cup B \cup C) \setminus I. Then B∪C⊆SB \cup C \subseteq S. Consider the truth assignment a which maps every variable vj,i∈Vv_{j,i} \in V to 00 if (vj,i)∈I(v_{j,i}) \in I, and to 11 otherwise, i.e., if (vj,i)∈S(v_{j,i}) \in S. Let us first show that a satisfies SS.

By construction, the clauses in S∩AS \cap A are satisfied by a. As by assumption ψ\psi contains at least one literal and its negation, the constructed assignment a maps at least one variable to 00, and so it satisfies BB as well. So a satisfies S∩(A∪B)S \cap(A \cup B). Since b is a satisfying truth assignment of ψ\psi, II contains a clause (v)(v) for at least one variable vv in each of the sets V1,…,VmV_1,\ldots,V_m. Hence, a maps to 00 at least one variable vv in each of the sets V1,…,VmV_1,\ldots,V_m. Hence, for every implication Lj,i∪Vj−1→vj,iL_{j,i} \cup V_{j-1} \to v_{j,i}, an element of the premise is set to 00 by a. Consequently a satisfies all the implications in CC, and so a satisfies SS.

Now, observe that since SS contains BB, it is not a subset of a solution in S1S_1. Since it contains CC, it is not a subset of a solution in S2S_2. Finally, since it contains one of every pair of clauses (vj,i)(v_{j,i}), (vj′,i′)(v_{j',i'}) such that vj′,i′∈Lj,iv_{j',i'} \in L_{j,i}, it is not a subset of a solution in S3S_3. Consequently, any greedy completion of SS leads to a maximal satisfiable subformula of ϕ\phi which is not in S1∪S2∪S3S_1 \cup S_2 \cup S_3. This completes the proof. ◇

Note that, given an nn-variable mm-clause 3-CNF ψ\psi, one may construct in polynomial time in n+mn+m a Horn expression ϕ\phi and the sets S1S_1, S2S_2 and S3S_3 as defined above, all of which of polynomial size in n+mn+m. 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 ψ\psi. 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 P=NPP = NP.

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. [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. [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. [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. [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. [5][Str19] Yann Strozecki. Enumeration complexity. Bulletin of EATCS, 1(129), 2019.
  6. [6][Tov84] Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete applied mathematics, 8(1):85–89, 1984.DOI

Paper details

vlnc:W_fh7f78g2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents