如果变量数量有很多子句，则在p中坐在p中吗？

Question

我定义a 长CNF 要包含至少$ 2^ frac {n} {2} $条款，其中$ n $是其变量的数量。令$ text {long-sat} = { phi： phi $是令人满意的长CNF公式$ } $。

我想知道为什么$ text {long-sat} in P $。首先，我认为这是$ text {npc} $，因为我可以从$ text {sat} $减少到$ text {long-sat} $，不是吗？

但是，也许我可以将$ text {2-sat} $减少到$ text {long-sat} $？我怎么做？

Answer 1

除非我缺少某些东西，否则它是微不足道的 p 随着公式的长度在变量的数量中为指数。因此，所有$ 2^{n} $真相分配可以在公式的长度中生成并在多项式时间内检查。

Answer 2

在这种情况下，答案是微不足道的 卢克指出. 。但是，正如您似乎自己提出了定义，请注意。

对于SAT，已经观察到有关可变计数与条款计数比率的所谓相变[1,2]。如果很小，实例很容易，如果很大，则很难。似乎或多或少从易于努力到硬的过渡。这似乎是一个 研究领域. cstheory.se 关于这种现象还有更多。

因此，如果您将“长”的定义调整为 多项式 爆炸，您确实可能会得到一个非平淡无奇的类 - 也就是说，在P中 - 仅仅是因为您的子句比变量要多得多。

---

1. SAT相过渡 IP Gent（1994）
2. 从特征“相变”确定计算复杂性 R. Monasson，R。Zecchina等。 （1999）