顽固/可触犯的可满足性问题变体的分类

Question

最近，我在论文[1]中发现了SAT的特殊对称版本，称为 2/2/4-SAT. 。但是有许多$ text {np} $ - 例如： 单调NAE-3SAT, 单调1英寸3-SAT, ...

其他一些变体是可处理的：$ 2 $ - $ text {sat} $，planar-nae- $ text {sat} $，...

是否有调查文件（或网页）对所有已证明为$ text {np} $ - 完整（或in $ text {p} $）进行分类的所有（怪异）$ text {sat} $变体？

---

1. 为$ n $ x $ n $的15个插头扩展找到最短的解决方案是棘手的 D. Ratner和M. Warmuth（1986）

Answer 1

经典，众所周知的结果

正如Standa Zivny关于CSTHEORY的相关问题所提到的， 哪些SAT问题很容易？, ，有一个众所周知的结果 Schaefer从1978年开始 （引用Zivny的答案）：

如果SAT在任何情况下都通过一组关系来参数，则只有6个可拖动的情况：2-SAT（即每个子句是二进制的），喇叭-SAT，双角，双 - 静音，仿射-SAT（线性的解决方案方程式 GF（2）），0-valid（由全0分配满足的关系）和1-valid（由全1分配满足的关系）。

Planar-3 Sat 意思是平面版本的 3sat 已知为$ Mathcal {np} $ - 完成。看 D Lichtenstein，《平面公式及其用途》，1981年. 。 3SAT的非平面版本当然是非常著名的经典$ Mathcal {np} $ - 完整问题。

不及格3SAT（NAE-3SAT）是$ Mathcal {np} $ - 完成。但是，它的平面版本在$ Mathcal {p} $中，如图所示 莫雷特（Moret），平面nae3sat在P，1988年.

最新和/或“怪异”变体

$ k $ - 油腻的单调NAE-3SAT

这是一个更具异国情调或怪异的变体，一个决策问题称为 $ k $ - 油腻的单调NAE-3SAT:

给定每个子句中的单调CNF表达式$ phi $，完全具有三个不同的变量，以便相应的约束图$ g（ phi）$ k色，是否可以满足expression $ phi $ note-qual-qualor。

在这里，相应的约束图$ g（ phi）$是与$ phi $关联的简单无向图，如下所示：$ phi $的每个变量是$ g $中的顶点，两个顶点在它们之间具有优势它们一起出现在一些条款中。

对于$ k = 4 $，问题是在$ mathcal {p} $中。对于$ k = 5 $，但是它是$ Mathcal {np} $ - 完成。看 P Jain，在单调NAE-3SAT和三角形剪切问题的变体中，2010年.

线性CNF变体

虽然也许不是异国情调或怪异，但有些众所周知的变体，即 nae-sat （不及格的SAT）和 XSAT （确切的SAT； 正是一个 每个条款中的字面意义至1和所有其他文字为0），在 线性 环境。线性公式成对的条款最多具有一个共同的一个变量。有趣的是，复杂性状态并不是Schaefer定理的遵循。

nae-sat 和 XSAT 保持$ Mathcal {np} $ - 仅限于线性公式时完成。而且， nae-sat 和 XSAT 仍然是$ Mathcal {np} $ - 仅包含长度至少$ k $的公式完成，对于每个固定整数$ k geq 3 $。它们是$ Mathcal {np} $ - 单调（无积极文字）线性公式的完整。然而， nae-sat 是在精确线性公式上可定义的多项式时间，其中每对不同的子句完全具有一个共同的一个变量。

关于复杂性的一些其他方面 nae-sat 和 XSAT 在某些假设下，可能仍然开放。有关更多细节，请参见 保罗申和施密特，关于线性公式的一些sat-variants，2009年 和 Porschen等人，线性XSAT问题的复杂性结果，2010年.