On the enumeration of signatures of XOR-CNF's
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 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), . , 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.Where the paper says it
Where the paper says it
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 , [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. 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.Where the paper says it
Where the paper says it
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 Namely,
we prove the following. The set of signatures of an XOR-CNF formula can be enumerated with
polynomial delay and polynomial space. 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.Where the paper says it
Where the paper says it
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 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]. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 Concerning the enumeration of minimal signatures, we show that the problem is in
fact equivalent to the case of listing maximal signatures. Proposition 1. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 ∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1
arXiv:2402. 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. 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. 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). 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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].Where the paper says it
Where the paper says it
Where the paper says it
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 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. Question 1. Can the maximal signatures of tractable CNF’s be enumerated in totalpolynomial time? 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
[BDM24] Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. p. 0 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, . ∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1
arXiv:2402.Where the paper says it
Where the paper says it
[BEG04] Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. p. 7 We refer to e. [BEG04, MS19] for a more detailed description of
this folklore technique. 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].Where the paper says it
Where the paper says it
[BEGK03] Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. p. 8 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. 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.Where the paper says it
Where the paper says it
[BKPS19] Endre Boros, Benny Kimelfeld, Reinhard Pichler, and Nicole Schweikardt. p. 1 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]. 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].Where the paper says it
Where the paper says it
[CGM+22] Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, and Luca Versari. p. 2 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]. 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.Where the paper says it
Where the paper says it
[CH96] Nadia Creignou and Miki Hermann. p. 0 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, . 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].Where the paper says it
Where the paper says it
[CH97] Nadia Creignou and Jean-Jacques Hébrard. p. 0 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, . 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].Where the paper says it
Where the paper says it
[CH11] Yves Crama and Peter L. p. 4 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.Where the paper says it
[CKM+19] Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive, and Heribert Vollmer. p. 0 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(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.Where the paper says it
Where the paper says it
[CMM+17] Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. p. 0 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, . ∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1
arXiv:2402.Where the paper says it
Where the paper says it
[COS11] Nadia Creignou, Frédéric Olive, and Johannes Schmidt. p. 0 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, . 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.Where the paper says it
Where the paper says it
[CU19] Alessio Conte and Takeaki Uno. New polynomial delay bounds for maximal subgraph enumeration by proximity search <ref:2402. p. 3 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.Where the paper says it
[EHR08] Khaled Elbassioni, Matthias Hagen, and Imran Rauf. Some fixedparameter tractable classes of hypergraph duality and related problems <ref:2402. p. 0 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.Where the paper says it
[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 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).Where the paper says it
[JYP88] David S. p. 1 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]). 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].Where the paper says it
Where the paper says it
[KBB+09] Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich, and Khaled Elbassioni. p. 8 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. 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.Where the paper says it
Where the paper says it
[KBE+05] Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. p. 8 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. , 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.Where the paper says it
Where the paper says it
[Sch78] Thomas J. p. 2 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]. , 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.Where the paper says it
Where the paper says it
[Str19] Yann Strozecki. p. 1 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]). ∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1
arXiv:2402.Where the paper says it
Where the paper says it
[TIAS77] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. p. 1 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]. 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].Where the paper says it
Where the paper says it
--- 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 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), . 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 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. , 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. , 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. , 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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].Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 We conclude by Proposition 3. 3 that the
extension problem can be solved in polynomial time for XOR-CNF signatures, hence
proving Theorem 1.Where the paper says it
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 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]. 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.Where the paper says it
Where the paper says it
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 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. 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]. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 Relying on these
results, we derive that maximal signatures enumeration for XOR-CNF’s is tractable. Namely, we obtain the following. ∗The authors have been supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). 1
arXiv:2402. There is a polynomial-delay algorithm generating the maximal (or minimal) signatures of a 2-XOR-CNF. To prove Theorem 1. 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. 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. 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].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles