跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

Given a CNF formula φ\varphi with clauses C1,…,CmC_1, \dots, C_m over a set of variables VV, a truth assignment a:V→{0,1}\mathbf{a} : V \to \{0, 1\} generates a binary sequence σφ(a)=(C1(a),…,Cm(a))σ_\varphi(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a})), called a signature of φ\varphi, where Ci(a)=1C_i(\mathbf{a})=1 if clause CiC_i evaluates to 1 under assignment a\mathbf{a}, and Ci(a)=0C_i(\mathbf{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.

作者备注:20 pages, 4 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-17 00:05 · 最新观测版本

On the enumeration of signatures of XOR-CNF's

Given a CNF formula φ\varphi with clauses C1,…,CmC_1, \dots, C_m over a set of variables VV, a truth assignment a:V→{0,1}\mathbf{a} : V \to \{0, 1\} generates a binary sequence σφ(a)=(C1(a),…,Cm(a))σ_\varphi(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a})), called a signature of φ\varphi, where Ci(a)=1C_i(\mathbf{a})=1 if clause CiC_i evaluates to 1 under assignment a\mathbf{a}, and Ci(a)=0C_i(\mathbf{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.

查看此版本解读 →查看此版本原文 ↗