查找$ epsilon'$ st $ l_ epsilon $ is $ mathsf {np} $ - 对于任何$ epsilon < epsilon'$而言很难

Question

令$ l_ epsilon $为所有$ 2 $ -cnf公式的语言，使得至少$（ frac {1} {2} {2} {2}+ epsilon）$ varphi $的条款可以是使满意。

我需要证明存在$ epsilon'$ st $ l_ epsilon $ is $ mathsf {np} $ - 对于任何$ epsilon < epsilon'$而言，很难。

我们知道，$ text {max} 2 text {sat} $可以大约为$ frac {55} {56} {56} $从$ text {max} 3 text {sat} $减少的条款。我应该如何解决这个问题？

Answer 1

在他的著名论文中 赫斯塔德 表明它比$ 21/22美元更好地近似Max2sat是NP-HARD。这可能意味着可以满足$ leq alpha $区分实例，并且可以满足$ geq（22/21） alpha $满足的实例，对于某些$ alpha geq 1/2 $。现在想象一下填充一个实例，使其成为新实例的$ p $分数，其余的恰好是$ 1/2 $ - 求解（例如，它由表单$ a land lnot a的条款组组成$）。现在的数字成为$ 1/2 + P（ alpha -1/2）$和$ 1/2 + P（（（22/21） alpha -1/2）$。后一个数字可以按照我们的意愿将其定为接近$ 1/2 $。

Answer 2

如果你知道 ε 是一个合理的数字，那么您不需要Max-2-Sat来证明您的语句。 Max-2-Sat的NP硬度的典型证明（例如，教科书中的一个 计算复杂性 由papadimitriou）实际上证明了NP的完整性 l_1/5. 。证明 l_ε 对于正理性数字 ε<1/5，我们可以减少 l_1/5 至 l_ε 如下：给定2CNF公式 φ （一个实例 l_1/5）， 让 m 是其中的子句。让 r 和 s 成为正整数，以至于（1/5--ε)先生 = 2εs 持有。然后构建一个2CNF公式（实例 l_ε）重复 φ 为了 r 时间和添加 s 成对矛盾的条款。一个简单的计算表明，这确实是从 l_1/5 至 l_ε.

这种减少显然只有在 ε 是理性的，因为否则 r 和 s 不能作为整数。一般情况 ε 正如Yuval Filmus在他的回答中写道的那样，不一定需要理性的。