论文标题
减少SAT到Max2xor
Reducing SAT to Max2XOR
论文作者
论文摘要
代表XOR子句（奇偶校验约束）的某些问题可以允许应用更有效的推理技术。在本文中，我们提出了一个用于将SAT子句转换为Max2xor约束的小工具，即最多2个变量的XOR子句等于零或一个。此外，我们为Max2xor问题提供了新的分辨率规则，该规则询问哪些是可以从一组2XOR方程来满足的最大约束数量。
Representing some problems with XOR clauses (parity constraints) can allow to apply more efficient reasoning techniques. In this paper, we present a gadget for translating SAT clauses into Max2XOR constraints, i.e., XOR clauses of at most 2 variables equal to zero or to one. Additionally, we present new resolution rules for the Max2XOR problem which asks for which is the maximum number of constraints that can be satisfied from a set of 2XOR equations.
