The Complexity of Making Unique Choices: Approximating 1-in- k SAT
The Complexity of Making Unique Choices: Approximating 1-in- k SAT
复制标题
做出独特选择的复杂性：近似 1-in-k SAT
DOI：
10.1007/11538462_9
复制
发表时间：
2005
影响因子：
18.9
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
V. Guruswami;L. Trevisan
我们研究 1-in-kSAT 的近似性，它是 Max kSAT 的变体，其中当子句的其中一个文字恰好满足时，则认为子句满足。我们还研究了该问题的不同特殊情况，包括通过限制文字为非否定和/或所有子句的大小恰好为 k 获得的情况。我们的结果表明，1-in-kSAT 问题在约束满足问题领域表现出一些相当特殊的现象。具体来说，当不允许文字否定时，问题变得更加容易以完美的完整性来近似。
We study the approximability of 1-in-kSAT, the variant of Max kSAT where a clause is deemed satisfied when precisely one of its literals is satisfied. We also investigate different special cases of the problem, including those obtained by restricting the literals to be unnegated and/or all clauses to have size exactly k. Our results show that the 1-in-kSAT problem exhibits some rather peculiar phenomena in the realm of constraint satisfaction problems. Specifically, the problem becomes substantially easier to approximate with perfect completeness as well as when negations of literals are not allowed.