Hardness of Max 3SAT with no mixed clauses
Hardness of Max 3SAT with no mixed clauses
复制标题
Max 3SAT 的硬度，无混合条款
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Subhash Khot
中科院分区：
文献类型：
--
作者：
V. Guruswami;Subhash Khot
我们研究了近似Max NM-E3 SAT的复杂性，这是Max 3SAT的一个变体，当实例保证没有任何混合子句时，即，每个子句的所有字面值都不被求反，或者都被求反。这是Guruswami（2004）引入的Max 3SAT的一个自然特例，其中还提出了这个变体是否可以在优于7/8的因子内近似的问题。我们证明了对于任意的/spl epsiv/ > 0，在7/8 + /spl epsiv/的因子内近似Max NM-E3 SAT是NP难的，因此这种变体并不比一般的Max 3SAT更容易近似。证明使用Dinur等人（2003）介绍的多层PCP技术，以避免折叠证明表的技术要求。规避此要求意味着PCP验证器可以使用它访问的位而无需额外的否定，这导致Max 3SAT的硬度没有任何混合子句。
We study the complexity of approximating Max NM-E3SAT, a variant of Max 3SAT when the instances are guaranteed to not have any mixed clauses, i.e., every clause has either all its literals unnegated or all of them negated. This is a natural special case of Max 3SAT introduced Guruswami (2004), where the question of whether this variant can be approximated within a factor better than 7/8 was also posed. We prove that it is NP-hard to approximate Max NM-E3SAT within a factor of 7/8 + /spl epsiv/ for arbitrary /spl epsiv/ > 0, and thus this variant is no easier to approximate than general Max 3SAT. The proof uses the technique of multilayered PCPs, introduced by Dinur et al. (2003), to avoid the technical requirement of folding of the proof tables. Circumventing this requirement means that the PCP verifier can use the bits it accesses without additional negations, and this leads to a hardness for Max 3SAT without any mixed clauses.