Sorting Parity Encodings by Reusing Variables
Sorting Parity Encodings by Reusing Variables
复制标题
DOI：
10.1007/978-3-030-51825-7_1
复制
发表时间：
2020-06-26
期刊：
影响因子：
--
通讯作者：
Heule MJ
中科院分区：
文献类型：
--
作者：
Chew L;Heule MJ
奇偶性推理对于CDCL求解器是具有挑战性的：反驳由两个矛盾的、不同顺序的适度大小的奇偶性约束组成的公式是困难的。两种替代方法可以有效地解决这些重新排序的奇偶公式：二元决策图和高斯消除（需要检测奇偶约束）。然而，这些技术的实现要么缺乏对证明日志的支持，要么引入了许多扩展变量。奇偶约束的紧凑、常用编码使用Tseitin变量。我们提出了一种技术，利用这些Tseitin变量重新排序的DRAT系统内的约束短条款的证明。我们对重序奇偶公式的反驳的大小是。
Parity reasoning is challenging for CDCL solvers: Refuting a formula consisting of two contradictory, differently ordered parity constraints of modest size is hard. Two alternative methods can solve these reordered parity formulas efficiently: binary decision diagrams and Gaussian Elimination (which requires detection of the parity constraints). Yet, implementations of these techniques either lack support of proof logging or introduce many extension variables. The compact, commonly-used encoding of parity constraints uses Tseitin variables. We present a technique for short clausal proofs that exploits these Tseitin variables to reorder the constraints within the DRAT system. The size of our refutations of reordered parity formulas is .
登录
查看更多内容
影响因子：
1.1
作者：
Warners, JP;van Maaren, H
通讯作者：
van Maaren, H
影响因子：
2.5
作者：
ROBINSON, JA
通讯作者：
ROBINSON, JA
DOI：
10.3233/978-1-58603-929-5-131
发表时间：
2009-01-01
期刊：
HANDBOOK OF SATISFIABILITY
影响因子：
--
作者：
Marques-Silva, Joao;Lynce, Ines;Malik, Sharad
通讯作者：
Malik, Sharad
影响因子：
2.5
作者：
DAVIS, M;PUTNAM, H
通讯作者：
PUTNAM, H
影响因子：
1.1
作者：
Li, CM
通讯作者：
Li, CM