← 研踪 PaperTrailarXiv:2402.18537 · v3
On the enumeration of signatures of XOR-CNF's
首次提交 2024-02-29 02:22
版本更新 2026-11-17 00:05
雷达观测 2026-11-17 16:10
摘要
Given a CNF formula with clauses over a set of variables , a truth assignment generates a binary sequence , called a signature of , where if clause evaluates to 1 under assignment , and 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.
作者备注:20 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-17 00:05 · 最新观测版本
On the enumeration of signatures of XOR-CNF's
Given a CNF formula with clauses over a set of variables , a truth assignment generates a binary sequence , called a signature of , where if clause evaluates to 1 under assignment , and 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.
查看此版本解读 →查看此版本原文 ↗