On the enumeration of signatures of XOR-CNF's

arXiv:2402.18537 · cs.DS, cs.DM, math.CO · Submitted 2024-02-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "On the enumeration of signatures of XOR-CNF's".

Jane: Here's the gist of the paper. Given a CNF formula with clauses over variables and truth assignments, a signature is defined as a binary sequence representing clause evaluations under an assignment <ref:2402.18537#pg2>.

Tom: The paper investigates the complexity of enumerating all, minimal, and maximal signatures for XOR-CNF formulas to characterize their computational limits <ref:2402.18537#pg7>.

Jane: The study focuses on listing all, minimal, and maximal signatures of a CNF formula where tractability is measured by total-polynomial time or output-polynomial time <ref:2402.18537#pg3>.

Tom: The authors note that generating all signatures of a CNF can be solved in total-polynomial time even though solutions cannot be recognized in polynomial time <ref:2402.18537#pg7>.

Paper summary: Tom: So we're talking about this paper called "On the enumeration of signatures of XOR-CNF's". Basically, it looks at how hard it is to list every possible signature of a formula where the clauses use an exclusive OR instead of a regular OR.

Jane: That sounds pretty technical, Tom. What exactly is a signature in this context? And why does XOR-CNF matter for enumeration problems?

Tom: Well, they define a signature as just the sequence you get when you plug in every possible truth assignment for the variables into the formula and record how each clause evaluates to one or zero. It’s like a fingerprint of all possible solutions <ref:2402.18537#pg2>.

Lu: The core idea they are pushing is that while finding all signatures for a regular CNF formula is hard, they focus on XOR-CNF because those clauses behave like systems of linear equations over the two element field F two <ref:2402.18537#pg4>.

Meng: Linear equations? That sounds good for computation, but how does that translate to actually generating the list of all signatures when there are a lot of variables? What’s the actual bottleneck they’re trying to solve here?

Jane: They're looking at three things: listing all signatures, minimal ones, and maximal ones. The paper claims that for XOR-CNF formulas, these enumeration problems become tractable under certain conditions <ref:2402.18537#pg7>.

Tom: Tractable how? Because they proved the set of signatures for an XOR-CNF formula can be enumerated with polynomial delay and polynomial space <ref:2402.18537#pg10>. That’s a big win because it means the runtime is bounded by something related to the size of the input and how many signatures you actually output <ref:2402.18537#pg3>.

Lu: They achieve that by showing that testing if a binary sequence is a signature reduces to satisfiability testing, and then proving the extension problem for XOR-CNF signatures is solvable in polynomial time <ref:2402.18537#pg10>. It's about mapping the enumeration problem onto something manageable.

Jane: That sounds like they're using algebraic tools to tame the complexity, which makes sense given how well XOR clauses work with Gaussian elimination <ref:2402.18537#pg4>. So, if we can solve satisfiability efficiently for these formulas, that helps us enumerate their signatures.

Meng: But what about the practical side? If I have a real system running on this XOR-CNF structure, is polynomial delay enough to handle the actual size of the output signature sequence? Does it break at scale?

Tom: That's where they go deeper into defining tractability. They introduce concepts like polynomial delay and incremental polynomial time as better ways to measure efficiency than just total polynomial time <ref:2402.18537#pg3>. It’s about controlling how the runtime grows as you generate more solutions.

Jane: And then they connect minimal and maximal signatures together, which is an interesting structural insight. They show that finding all minimal signatures is equivalent to listing all maximal ones <ref:2402.18537#pg7>.

Lu: That equivalence comes from Proposition one point two, which links the enumeration of minimal signatures directly to that of maximal signatures <ref:2402.18537#pg8>. If you can solve one enumeration problem efficiently, you can solve the other too.

Paper summary: Meng: So if I want to find the most extreme examples—the maximal ones—I get the same algorithmic tractability as finding the smallest ones? That’s a useful trade-off for deployment, I guess.

Tom: Exactly. And for two XOR-CNF formulas, specifically those using only disequalities like x not equal to y, they relate it to enumerating maximal bipartite subgraphs <ref:2402.18537#pg5>. They have a polynomial delay algorithm generating those maximal signatures <ref:2402.18537#pg17>.

Jane: That connection to graph theory is interesting. So, for the most basic XOR formulas, we can relate the signature enumeration problem to finding specific structures in graphs <ref:2402.18537#pg4>.

Lu: They even establish that the enumeration of minimal signatures is equivalent to that of maximal signatures <ref:2402.18537#pg7>, reinforcing that link again. It’s a strong structural result for this class of formulas.

Meng: What about the open questions? The paper flags some things they haven't solved yet, like whether Theorem one point three can be improved to polynomial delay <ref:2402.18537#pg18>. That means they aren't totally sure if that incremental-polynomial time algorithm is the best possible one for every case.

Tom: And they ask if maximal signatures of two XOR-CNF can be generated with polynomial delay and polynomial space <ref:2402.18537#pg18>. They suggest that some approaches, like flashlight search, might not work for that specific question because of the NP-completeness result for the extension problem <ref:2402.18537#pg20>.

Jane: That points to a frontier where things are still open. The hardness results they mention, like the NP-complete result for finding a maximal bipartite subgraph, show that even in this tractable class, there are related problems that remain computationally hard <ref:2402.18537#pg19>.

Lu: They also look at other formula types, like Horn or two-CNF formulas, and those are still open questions regarding the tractability of their maximal signatures <ref:2402.18537#pg20>. It shows that XOR-CNF is a specific success story, not the whole field.

Meng: From an engineering standpoint, knowing which class of formulas is tractable for enumeration tells me which structures I can rely on for generating test cases or verifying properties at scale <ref:2402.18537#pg18>. That's where it matters for production systems.

Tom: So, to wrap up this paper, the main point is that XOR-CNF formulas have a structure—being linear equations over F two—that lets us use algebraic tools to make signature enumeration tractable <ref:2402.18537#pg3>.

Jane: And it gives us a clear picture of what’s achievable for these specific structures, showing tractability for all, minimal, and maximal signatures under polynomial delay or output-polynomial time <ref:2402.18537#pg7>.

Lu: It connects algebraic properties to graph theory beautifully, and it sets up a strong equivalence between the enumeration of minimal and maximal signatures <ref:2402.18537#pg8>.

Meng: The implication for me is that if we can model a problem using XOR constraints, we might be able to generate all possible scenarios efficiently instead of brute-forcing them <ref:2402.18537#pg10>.

Tom: It definitely shows how the algebraic properties of the formula directly dictate the complexity of generating its signature set, which is a key principle for model analysis <ref:2402.18537#pg4>.

Conclusion: Tom: So we've been looking at how to list all possible signatures for XOR formulas, like those using exclusive OR instead of regular or logic <ref:2402.18537#pg4>.

Jane: Right, so it boils down to how hard it is to generate every single possible way a formula can look when you plug in truth values <ref:2402.18537#pg2>.

Tom: The authors show that for XOR formulas, this enumeration isn't impossible; they found ways to do it with polynomial delay and polynomial space <ref:2402.18537#pg10>.

Jane: And they proved that finding the smallest signatures is actually just as easy as finding the largest ones, which is a neat structural link <ref:2402.18537#pg8>.

Tom: It's about showing that if you can manage one of those extremes, you can manage the other one too <ref:2402.18537#pg7>.

Jane: So, what does this mean for us? It means that for these specific XOR structures, we have an algorithmic path to explore every possible signature without getting stuck in exponential time immediately <ref:2402.18537#pg3>.

Tom: It gives us a clear computational boundary for how complex these formulas can get when we're trying to map out their solution space <ref:2402.18537#pg4>.

Jane: But the paper also points out some open questions, like whether they can improve those delays or if they can solve it with even less memory <ref:2402.18537#pg18>.

Tom: Exactly. It means there's still room to optimize the algorithms and see if we can push the limits of what's possible with this approach <ref:2402.18537#pg18>.

Jane: And that leads us into how these algebraic ideas connect to graph theory and matroid theory, which is where things get really interesting <ref:2402.18537#pg4>.

Nadia Creignou, Oscar Defrain, Frédric Olive, Simon Vilmin

Aix-Marseille University · CNRS

cs.DS, cs.DM, math.CO

Submitted: 2024-02-28

Updated: 2026-11-16

Comments: 20 pages, 4 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: Given a CNF formula with clauses over variables and truth assignments, a signature is defined as a binary sequence representing clause evaluations under an assignment <ref:2402.18537#pg2>.

Key concepts

Signature
A signature is a binary sequence that represents how a specific truth assignment evaluates every clause in the CNF formula. It's essentially a fingerprint of the formula under a given assignment, where each bit indicates whether its corresponding clause is satisfied (1) or not (0).
XOR-CNF
XOR-CNF formulas are a type of logical formula where clauses are connected by the exclusive-or connective instead of the standard 'or'. This structure is important because it allows the formula to be treated algebraically as a system of linear equations over the two-element field F2, enabling efficient solving techniques like Gaussian elimination.
Maximal Signature
A maximal signature is one that cannot be extended by changing a single truth assignment while maintaining its properties. The paper shows that finding these signatures for XOR-CNF can be done efficiently; for 2-XOR-CNF, this enumeration is linked to the problem of finding maximal bipartite subgraphs in a related graph.

Terminology

Summary

Given a CNF formula with clauses over variables and truth assignments, a signature is defined as a binary sequence representing clause evaluations under an assignment <ref:2402. p. 0

Where the paper says it

February 28, 2024 Abstract Given a CNF formula φ with clauses C1, . , Cm over a set of variables V , a truth assignment a: V → {0, 1} generates a binary sequence σφ(a) = (C1(a), .

18537#pg2>. The paper investigates the complexity of enumerating all, minimal, and maximal signatures for XOR-CNF formulas to characterize their computational limits <ref:2402. p. 0
Where the paper says it

, those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s.

18537#pg7>.

Introduction to Signature Enumeration Complexity

The study focuses on listing all, minimal, and maximal signatures of a CNF formula where tractability is measured by total-polynomial time or output-polynomial time <ref:2402.18537#pg3>. The authors note that generating all signatures of a CNF can be solved in total-polynomial time even though solutions cannot be recognized in polynomial time <ref:2402. p. 1

Where the paper says it

, [JYP88, Str19]). Generating all the signatures of a CNF turns out to be of great fundamental interest, for it is an example of enumeration problem which can be solved in totalpolynomial time even though solutions cannot be recognized in polynomial time.

18537#pg7>. They define tractability as running in total-polynomial time or output-polynomial time, and introduce concepts like polynomial delay and incremental-polynomial time <ref:2402. p. 1
Where the paper says it

Instead, output-sensitive complexity estimates the running time of an enumeration algorithm using both input and output sizes. In that framework, an algorithm is considered tractable when it runs in total-polynomial time (or output-polynomial time), that is, if its execution time is bounded by a polynomial in the combined size of the input and the output.

18537#pg3>.

Tractability of XOR-CNF Signatures

The paper explores XOR-CNF formulas because their algebraic properties allow them to be seen as systems of linear equations over the two-element field F2 <ref:2402.18537#pg4>. The authors prove that the set of signatures of an XOR-CNF formula can be enumerated with polynomial delay and polynomial space <ref:2402. p. 2

Where the paper says it

Namely, we prove the following. The set of signatures of an XOR-CNF formula can be enumerated with polynomial delay and polynomial space.

18537#pg10>. This is achieved by showing that testing whether a binary sequence is a signature reduces to satisfiability testing, and the extension problem for XOR-CNF signatures is solvable in polynomial time <ref:2402. p. 6
Where the paper says it

3 Signatures of XOR-CNF’s and their properties We prove that testing whether a binary sequence is a signature (resp. minimal signature, maximal signature) of an XOR-CNF can be done in polynomial time in the size of the CNF at hand, and use it to show that listing all signatures of an XOR-CNF is tractable.

18537#pg10>.

Characterization of Maximal Signatures

The enumeration of maximal signatures for an XOR-CNF is shown to be tractable by relating it to other problems in graph theory and matroid theory <ref:2402.18537#pg4>. Specifically, the case of 2-XOR-CNF is related to the enumeration of maximal bipartite subgraphs <ref:2402. p. 2

Where the paper says it

Specifically, we show the case of 2-XOR-CNF to generalize maximal bipartite subgraphs enumeration, a problem which was recently shown to admit a polynomial-delay algorithm [CGM+22]. As of the general case of XOR-CNF’s, it can be seen as listing all maximal satisfiable subsystems of a linear system of equations, which is related to the enumeration of circuits passing through a given element in a matroid [BEGK03]; see also [KBB+09, KBE+05].

18537#pg5>. Theorem 1.4 establishes that there is a polynomial-delay algorithm generating the maximal signatures of a 2-XOR-CNF <ref:2402. p. 3
Where the paper says it

There is an incremental-polynomial time algorithm generating the maximal (or minimal) signatures of an XOR-CNF. Concerning the case of 2-XOR-CNF, we show it to be even more tractable, that is, we show that it can be solved with polynomial delay using proximity search.

18537#pg17>. This result relies on representing the input as an edge-bicolored multigraph and relating maximal signatures to maximal red-blue bipartite subgraphs. p. 3
Where the paper says it

4, we represent the input 2-XOR-CNF as an edge-bicolored multigraph where each color codes the parity of the XOR clause. Then, the enumeration amounts to list maximal bipartite subgraphs with additional constraints on colored edges.

Equivalence of Minimal and Maximal Signatures

The paper establishes a strong relationship between minimal and maximal signatures for XOR-CNF formulas <ref:2402.18537#pg7>. Proposition 3. p. 2

Where the paper says it

Concerning the enumeration of minimal signatures, we show that the problem is in fact equivalent to the case of listing maximal signatures. Proposition 1.

1 states that a sequence is a minimal signature of φ if and only if it is a maximal signature of φ¯, which implies the equivalence of their enumeration problems <ref:2402. p. 6
Where the paper says it

3 Signatures of XOR-CNF’s and their properties We prove that testing whether a binary sequence is a signature (resp. minimal signature, maximal signature) of an XOR-CNF can be done in polynomial time in the size of the CNF at hand, and use it to show that listing all signatures of an XOR-CNF is tractable.

18537#pg8>. Furthermore, the enumeration of minimal signatures for an XOR-CNF is shown to be equivalent to that of maximal signatures <ref:2402. p. 2
Where the paper says it

The set of signatures of an XOR-CNF formula can be enumerated with polynomial delay and polynomial space. Concerning the enumeration of minimal signatures, we show that the problem is in fact equivalent to the case of listing maximal signatures.

18537#pg7>.

Limitations and Future Directions

The authors discuss open questions regarding the improvement of existing algorithms, such as whether Theorem 1.3 can be improved to polynomial delay <ref:2402. p. 0

Where the paper says it

∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1 arXiv:2402.

18537#pg18>. They also address Question 3, asking if maximal signatures of a 2-XOR-CNF can be generated with polynomial delay and polynomial space <ref:2402. p. 2
Where the paper says it

The set of signatures of an XOR-CNF formula can be enumerated with polynomial delay and polynomial space. Concerning the enumeration of minimal signatures, we show that the problem is in fact equivalent to the case of listing maximal signatures.

18537#pg18>. The NP-completeness result for the extension problem suggests that flashlight search may not be adapted to give a positive answer to Question 3 <ref:2402. p. 3
Where the paper says it

4 to use polynomial space, it would imply such a result for maximal bipartite subgraphs enumeration, another open question [CGM+22]. Toward such directions, we prove that the folklore technique of flashlight search used to obtain Theorem 1.

18537#pg20>. They also point out open questions concerning the tractability of maximal signatures for Horn and 2-CNF formulas <ref:2402. p. 1
Where the paper says it

Among tractable formulas, Horn and 2-CNF’s are two natural candidates for approaching Question 1. These two cases however proved to be very challenging, and the question of their tractability was explicitly stated as an open problem in the 2022’s edition of the Workshop on Enumeration Problems and Applications (WEPA’22).

18537#pg20>. The work suggests that improving the algorithm to run with FPT-delay parameterized by k plus ω seems open <ref:2402. p. 3
Where the paper says it

In both cases, getting rid of a potentially exponential space use is a natural enhancement one may seek. It should however be noted that improving the algorithm from [BEGK03] to get polynomial space is open for two decades now.

18537#pg20>.

Conclusion on 2-XOR-CNF

For 2-XOR-CNF formulas consisting only of disequalities x!= y, the enumeration of maximal signatures is equivalent to the enumeration of maximal bipartite subgraphs <ref:2402. p. 0

Where the paper says it

Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s. Keywords: algorithmic enumeration, XOR-CNF, signatures, maximal bipartite subgraphs enumeration, extension, proximity search.

18537#pg17>. Corollary 4.4 states that there is a polynomial-delay algorithm listing these maximal signatures <ref:2402. p. 1
Where the paper says it

They give an incremental-polynomial time algorithm for listing all the signatures of a k-CNF for fixed k, and show that for tractable CNF’s, signatures can be enumerated with polynomial delay. On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration.

18537#pg17>. The overall conclusion is that the enumeration of all, minimal, and maximal signatures for XOR-CNF formulas is tractable under certain conditions <ref:2402. p. 1
Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

18537#pg18>.

Final Remarks on Complexity

The paper concludes by stating that the problem of deciding whether there exists a maximal bipartite (edge) subgraph H of G such that A ⊆ E(H) and B ∩ E(H) = ∅ is NP-complete <ref:2402.18537#pg19>. This hardness result is derived via reduction from 3-SAT <ref:2402. p. 1

Where the paper says it

Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77]. As of their hardness result, it relies on the fact that the existence of at least two solutions would imply the non-satisfiability of the CNF at hand.

18537#pg19>. The work contributes to the open question of whether maximal signatures of tractable CNF’s can be enumerated in total-polynomial time <ref:2402. p. 1
Where the paper says it

Question 1. Can the maximal signatures of tractable CNF’s be enumerated in totalpolynomial time?

18537#pg20>. The paper provides a framework for analyzing XOR-CNF signatures using algebraic, matroid, and graph concepts <ref:2402. p. 2
Where the paper says it

This ability to capture XOR clauses using algebraic, matroid, and graph concepts and methods provides efficient tools for analyzing their behavior with respect to our enumeration problem. Note that these formulas do not fall in the framework of CNF’s though.

18537#pg4>. The authors also remark that duplicate clauses in φ may be ignored without loss of generality <ref:2402. p. 5
Where the paper says it

Indeed, having one of these clauses evaluated to 1 implies that each of its copies is also evaluated to 1. Hence, we will assume without loss of generality that all formulas are without duplicated clauses in the rest of the paper, i.

18537#pg7>.

References

[BBČ+21] Kristóf Bérczi, Endre Boros, Ondřej Čepek, Khaled Elbassioni, Petr Kučera, and Kazuhisa Makino. Generating clause sequences of a CNF formula <ref:2402. p. 4

Where the paper says it

We say that C is a k-clause if |C| ≤ k. A formula in conjunctive normal form (or a CNF for short) φ is a conjunction of clauses, i.

18537#pg7>.

[BDM24] Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension <ref:2402. p. 0
Where the paper says it

∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1 arXiv:2402.

18537#pg22>.

[BEG04] Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. p. 7

Where the paper says it

We refer to e. [BEG04, MS19] for a more detailed description of this folklore technique.

Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems <ref:2402. p. 1
Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

18537#pg22>.

[BEGK03] Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. p. 8

Where the paper says it

More precisely, we prove the general case to be solvable in incremental-polynomial time by a result of Boros et al. [BEGK03], and the 2-XOR-CNF case to be solvable with polynomial delay using proximity search.

Algorithms for enumerating circuits in matroids <ref:2402. p. 8
Where the paper says it

Hence φ can be seen as a system of linear equations whose maximal feasible subsystems correspond to its maximal signatures. In [BEGK03], the authors present an incremental polynomial-time algorithm for enumerating all circuits of a matroid containing an element, and more generally, one for enumerating all maximal subsets not spanning an element.

18537#pg22>.

[BKPS19] Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt. p. 1

Where the paper says it

In this paper, we investigate the problems of listing all, minimal, and maximal signatures of a CNF, where minimal and maximal are meant bitwise. The task of finding all signatures of a CNF originates from well-designed pattern trees and has first been posed during the Dagstuhl seminar on enumeration in data management [BKPS19].

Enumeration in Data Management (Dagstuhl Seminar 19211) <ref:2402. p. 1
Where the paper says it

In this paper, we investigate the problems of listing all, minimal, and maximal signatures of a CNF, where minimal and maximal are meant bitwise. The task of finding all signatures of a CNF originates from well-designed pattern trees and has first been posed during the Dagstuhl seminar on enumeration in data management [BKPS19].

18537#pg7>.

[CGM+22] Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, and Luca Versari. p. 2

Where the paper says it

Quite surprisingly, we prove this problem to relate well with other problems from graph theory and matroid theory. Specifically, we show the case of 2-XOR-CNF to generalize maximal bipartite subgraphs enumeration, a problem which was recently shown to admit a polynomial-delay algorithm [CGM+22].

Proximity search for maximal subgraph enumeration <ref:2402. p. 0
Where the paper says it

Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s. Keywords: algorithmic enumeration, XOR-CNF, signatures, maximal bipartite subgraphs enumeration, extension, proximity search.

18537#pg11>.

[CH96] Nadia Creignou and Miki Hermann. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

Complexity of generalized satisfiability counting problems <ref:2402. p. 2
Where the paper says it

XOR-clauses were revealed in Schaefer’s famous complexity classification as a tractable case for deciding the satisfiability of a set of generalized clauses [Sch78]. Interestingly, XOR-clauses are the only ones that lead to a tractable case when it comes to counting the number of satisfying assignments [CH96].

18537#pg6>.

[CH97] Nadia Creignou and Jean-Jacques Hébrard. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

On generating all solutions of generalized satisfiability problems <ref:2402. p. 2
Where the paper says it

Another natural step toward answering Question 1 is to consider XOR-CNF formulas, being conjunctions of clauses using the “exclusive-or” connective instead of the usual “or” connective. XOR-clauses were revealed in Schaefer’s famous complexity classification as a tractable case for deciding the satisfiability of a set of generalized clauses [Sch78].

18537#pg6>.

[CH11] Yves Crama and Peter L. p. 4

Where the paper says it

For an XOR-CNF φ = C1 ∧ · · · ∧ Cm, we denote by φ¯ the XOR-CNF C¯ 1 ∧ · · · ∧ C¯m and call it the inverse of φ. We recall that the satisfiability of an XOR-CNF can be tested in polynomial time [CH11, Theorem 2.

Hammer. Boolean functions: Theory, algorithms, and applications <ref:2402.18537#pg6>.

[CKM+19] Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive, and Heribert Vollmer. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

Parameterised enumeration for modification problems <ref:2402. p. 0
Where the paper says it

, Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration.

18537#pg22>.

[CMM+17] Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

Paradigms for parameterized enumeration <ref:2402. p. 0
Where the paper says it

∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1 arXiv:2402.

18537#pg21>.

[COS11] Nadia Creignou, Frédéric Olive, and Johannes Schmidt. p. 0

Where the paper says it

On the enumeration of signatures of XOR-CNF’s∗ Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024 Abstract Given a CNF formula φ with clauses C1, .

Enumerating all solutions of a boolean CSP by non-decreasing weight <ref:2402. p. 1
Where the paper says it

Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77]. As of their hardness result, it relies on the fact that the existence of at least two solutions would imply the non-satisfiability of the CNF at hand.

18537#pg6>.

[CU19] Alessio Conte and Takeaki Uno. New polynomial delay bounds for maximal subgraph enumeration by proximity search <ref:2402. p. 3

Where the paper says it

There is an incremental-polynomial time algorithm generating the maximal (or minimal) signatures of an XOR-CNF. Concerning the case of 2-XOR-CNF, we show it to be even more tractable, that is, we show that it can be solved with polynomial delay using proximity search.

18537#pg22>.

[EHR08] Khaled Elbassioni, Matthias Hagen, and Imran Rauf. Some fixedparameter tractable classes of hypergraph duality and related problems <ref:2402. p. 0

Where the paper says it

They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.

18537#pg20>.

[GKKL22] Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined notions of parameterized enumeration kernels with applications to matching cut enumeration <ref:2402. p. 1

Where the paper says it

Among tractable formulas, Horn and 2-CNF’s are two natural candidates for approaching Question 1. These two cases however proved to be very challenging, and the question of their tractability was explicitly stated as an open problem in the 2022’s edition of the Workshop on Enumeration Problems and Applications (WEPA’22).

18537#pg20>.

[JYP88] David S. p. 1

Where the paper says it

Incremental-polynomial time, on the other hand, means that the time to produce the i th solution is bounded by a polynomial in the input size plus i (see e. , [JYP88, Str19]).

Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets <ref:2402. p. 1
Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

18537#pg7>.

[KBB+09] Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich, and Khaled Elbassioni. p. 8

Where the paper says it

4 Maximal signatures of XOR-CNF’s We investigate the complexity of enumerating the maximal signatures of a given XORCNF. More precisely, we prove the general case to be solvable in incremental-polynomial time by a result of Boros et al.

Generating all vertices of a polyhedron is hard <ref:2402. p. 0
Where the paper says it

In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard.

18537#pg22>.

[KBE+05] Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. p. 8

Where the paper says it

4 Maximal signatures of XOR-CNF’s We investigate the complexity of enumerating the maximal signatures of a given XORCNF. More precisely, we prove the general case to be solvable in incremental-polynomial time by a result of Boros et al.

On the complexity of some enumeration problems for matroids <ref:2402. p. 0
Where the paper says it

, Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration.

18537#pg22>.

[Sch78] Thomas J. p. 2

Where the paper says it

Another natural step toward answering Question 1 is to consider XOR-CNF formulas, being conjunctions of clauses using the “exclusive-or” connective instead of the usual “or” connective. XOR-clauses were revealed in Schaefer’s famous complexity classification as a tractable case for deciding the satisfiability of a set of generalized clauses [Sch78].

Schaefer. The complexity of satisfiability problems <ref:2402. p. 0
Where the paper says it

, those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s.

18537#pg7>.

[Str19] Yann Strozecki. p. 1

Where the paper says it

Incremental-polynomial time, on the other hand, means that the time to produce the i th solution is bounded by a polynomial in the input size plus i (see e. , [JYP88, Str19]).

Enumeration complexity <ref:2402. p. 0
Where the paper says it

∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1 arXiv:2402.

18537#pg7>.

[TIAS77] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. p. 1

Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

A new algorithm for generating all the maximal independent sets <ref:2402. p. 1
Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

18537#pg7>.

--- Page 1 ---

On the enumeration of signatures of XOR-CNF’s

Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin Aix-Marseille Université, CNRS, LIS, Marseille, France. February 28, 2024

Abstract

Given a CNF formula φ with clauses C1,..., Cm over a set of variables V, a truth assignment a: V → 0, 1 generates a binary sequence σφ(a) = (C1(a),. p. 0

Where the paper says it

February 28, 2024 Abstract Given a CNF formula φ with clauses C1, . , Cm over a set of variables V , a truth assignment a: V → {0, 1} generates a binary sequence σφ(a) = (C1(a), .

p. 0
Where the paper says it

February 28, 2024 Abstract Given a CNF formula φ with clauses C1, . , Cm over a set of variables V , a truth assignment a: V → {0, 1} generates a binary sequence σφ(a) = (C1(a), .

.., Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise <ref:2402. p. 0
Where the paper says it

, Cm over a set of variables V , a truth assignment a: V → {0, 1} generates a binary sequence σφ(a) = (C1(a), . , Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise.

p. 0
Where the paper says it

, Cm over a set of variables V , a truth assignment a: V → {0, 1} generates a binary sequence σφ(a) = (C1(a), . , Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise.

18537#pg2>. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration <ref:2402. p. 0
Where the paper says it

, Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration.

p. 0
Where the paper says it

, Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration.

18537#pg7>.

Pruning redundant reasoning tokens

Given a CNF formula φ with clauses C1,..., Cm over a set of variables V, a truth assignment a: V → 0, 1 generates a binary sequence σφ(a) = (C1(a),..., Cm(a)), called a signature of φ, where Ci(a) = 1 if clause Ci evaluates to 1 under assignment a, and Ci(a) = 0 otherwise <ref:2402.18537#pg2>. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration <ref:2402.18537#pg7>.

How the training signal is built

The paper investigates the problems of listing all, minimal, and maximal signatures of a CNF, where minimal and maximal are meant bitwise <ref:2402.18537#pg3>. The task of finding all signatures of a CNF originates from well-designed pattern trees and has first been posed during the Dagstuhl seminar on enumeration in data management [BKPS19] <ref:2402. p. 1

Where the paper says it

In this paper, we investigate the problems of listing all, minimal, and maximal signatures of a CNF, where minimal and maximal are meant bitwise. The task of finding all signatures of a CNF originates from well-designed pattern trees and has first been posed during the Dagstuhl seminar on enumeration in data management [BKPS19].

18537#pg7>.

Where the gains come from

The authors investigate XOR-CNF formulas, being conjunctions of clauses using the “exclusive-or” connective instead of the usual “or” connective <ref:2402.18537#pg4>. XOR-clauses are tractable because they can be seen as a system of linear equations over the 2-element field F2 <ref:2402. p. 2

Where the paper says it

The success of XOR-clauses is due to their algebraic properties. Indeed, a set of such clauses can be seen as a system of linear equations over the 2-element field.

18537#pg4>. This algebraic structure allows for efficient tools such as Gaussian elimination and matroid algorithms <ref:2402. p. 2
Where the paper says it

As a result, the sets of satisfying assignments of such subsets are affine subspaces, and they allow for algebraic tools such as Gaussian elimination and matroid algorithms. Also in the special case of 2-XOR clauses, subsets of clauses can be interpreted as graphs with 0/1-labeled edges and benefit from several efficient graph algorithms, e.

18537#pg4>.

The authors prove that the set of signatures of an XOR-CNF formula can be enumerated with polynomial delay and polynomial space <ref:2402.18537#pg10>. This is done by showing that the extension problem for XOR-CNF signatures is solvable in polynomial time <ref:2402. p. 8

Where the paper says it

We conclude by Proposition 3. 3 that the extension problem can be solved in polynomial time for XOR-CNF signatures, hence proving Theorem 1.

18537#pg10>.

The paper shows that the enumeration of minimal signatures is equivalent to listing maximal signatures, as there is a polynomial-delay and polynomial space algorithm listing all minimal signatures if and only if there is one listing all maximal signatures <ref:2402.18537#pg7>. This equivalence stems from Proposition 1. p. 1

Where the paper says it

On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration. Their positive result relies on the equivalence with maximal independent sets enumeration in graphs, known to be tractable [TIAS77].

2 which links the enumeration of minimal signatures to that of maximal signatures <ref:2402. p. 0
Where the paper says it

Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s. Keywords: algorithmic enumeration, XOR-CNF, signatures, maximal bipartite subgraphs enumeration, extension, proximity search.

18537#pg8>.

Maximal Signatures Enumeration for XOR-CNF

The problem is shown to relate well with other problems from graph theory and matroid theory, specifically showing the case of 2-XOR-CNF generalizes maximal bipartite subgraphs enumeration <ref:2402.18537#pg4>. Theorem 1.3 shows that there is an incremental-polynomial time algorithm generating the maximal (or minimal) signatures of an XOR-CNF <ref:2402. p. 3

Where the paper says it

There is an incremental-polynomial time algorithm generating the maximal (or minimal) signatures of an XOR-CNF. Concerning the case of 2-XOR-CNF, we show it to be even more tractable, that is, we show that it can be solved with polynomial delay using proximity search.

18537#pg5>. Specifically, for 2-XOR-CNF, Theorem 1. p. 2
Where the paper says it

Quite surprisingly, we prove this problem to relate well with other problems from graph theory and matroid theory. Specifically, we show the case of 2-XOR-CNF to generalize maximal bipartite subgraphs enumeration, a problem which was recently shown to admit a polynomial-delay algorithm [CGM+22].

4 proves there is a polynomial-delay algorithm generating the maximal (or minimal) signatures <ref:2402. p. 1
Where the paper says it

They give an incremental-polynomial time algorithm for listing all the signatures of a k-CNF for fixed k, and show that for tractable CNF’s, signatures can be enumerated with polynomial delay. On the other hand, they show that generating maximal signatures is hard, while minimal signatures can be listed with polynomial delay, regardless of the CNF under consideration.

18537#pg17>.

Final Summary of Results

The work demonstrates that enumerating all (resp. minimal, maximal) signatures of an XOR-CNF formula is tractable, namely Theorems 1. p. 2

Where the paper says it

Relying on these results, we derive that maximal signatures enumeration for XOR-CNF’s is tractable. Namely, we obtain the following.

1, 1.3 and 1.4 <ref:2402. p. 0
Where the paper says it

∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1 arXiv:2402.

18537#pg7>. The algorithm of Theorem 1. p. 3
Where the paper says it

There is a polynomial-delay algorithm generating the maximal (or minimal) signatures of a 2-XOR-CNF. To prove Theorem 1.

3 runs in incremental-polynomial time while the other two run with polynomial delay <ref:2402. p. 7
Where the paper says it

We recall that the main idea of this technique is to conduct binary search over the space of solutions. In order for flashlight search to run with polynomial delay and polynomial space, it is sufficient to solve the so-called “extension problem” in polynomial time: given two disjoint subsets A, B of the ground set, decide whether there exists a solution including A and avoiding B.

18537#pg7>. The paper addresses open questions about polynomial delay for maximal signatures <ref:2402. p. 0
Where the paper says it

Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al.

18537#pg7>. The final results show that the enumeration of maximal signatures of a 2-XOR-CNF is equivalent to enumerating maximal red-blue bipartite subgraphs <ref:2402. p. 2
Where the paper says it

Quite surprisingly, we prove this problem to relate well with other problems from graph theory and matroid theory. Specifically, we show the case of 2-XOR-CNF to generalize maximal bipartite subgraphs enumeration, a problem which was recently shown to admit a polynomial-delay algorithm [CGM+22].

18537#pg17>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Efficient enumeration of XOR-CNF signatures: The system can enumerate all signatures of an XOR-CNF formula with polynomial delay and polynomial space, leveraging a reduction to maximal bipartite subgraph enumeration for 2-XOR-CNFs.

  2. Maximal signature generation for 2-XOR-CNF: The system can generate the maximal (or minimal) signatures of a 2-XOR-CNF using proximity search, achieving polynomial delay even with polynomial space, based on Theorem 1.4 and its reduction to maximal red blue bipartite subgraphs.

  3. Tractable enumeration for general XOR-CNF signatures: The system can enumerate all signatures of an XOR-CNF formula in total polynomial time by solving the extension problem in polynomial time for the signature constraints, as shown in Theorem 1.1.

  4. Bipartite subgraph enumeration application: The system can solve the decision problem of finding a maximal bipartite (edge) subgraph H of a graph G containing specific edge sets A and avoiding others B, which is NP-complete, by using reductions from 3-SAT to construct such problems.

Abstract

Given a CNF formula φ with clauses C 1,, C m over a set of variables V, a truth assignment a: V to 0, 1 generates a binary sequence σ φ(a)=(C 1(a),, C m(a)), called a signature of φ, where C i(a)=1 if clause C i evaluates to 1 under assignment a, and C i(a)=0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

Related papers