NP类的外面与P类的里面

【PSPACE完全性与QBF问题】
对于PSPACE复杂性类，我们也有PSPACE完全类：
定义. 如果\(\forall L' \in_m PSPACE,L'\le L\)，称L是PSPACE难的。如果还有\(L\in PSPACE\)，称L是PSPACE完全的。

例. 全量化的布尔公式问题(QBF)是PSPACE完全的：
任给一个\(\{\lor, \land, \lnot\}\)上的封闭的前束范式\(\phi,\)问其值是否为1？
封闭是指公式中没有自由变元。

一方面，\(QBF\in PSPACE.\)采取递归算法，若\(\phi = \forall x \psi (x),\)分别计算\(\psi(0),\psi(1)\)；对\(\phi = \exists x \psi (x)\)作类似处理。
另一方面，类似Cook定理的证明，用一组表示U的状态、读写头位置和方格内容的变元来描述格局，一个格局的变元数为\(l=O(n^k).\)设\(\phi_i(A,B)\)表示至多\(2^i\)步是否能从A格局变为B格局。令\[\phi_x = \exists C_0 \exists C_f(F_0(C_0)\land F_f(C_f)\land \phi_{cn^k}(C_0,C_f)),\]\(C_0,C_f\)分别为初始和接受格局。之后同Cook定理证明非常类似。

【2SAT问题】
如果限制每一个简单析取式恰有k个文字，这样的合取范式称为k合取范式，记作kCNF，对应的可满足问题记作kSAT。已知3SAT是NP完全的，因此对任何\(k\ge 3,\) kSAT都是NP完全的。对于k=2，我们有：
例. \(2SAT \in P.\)
设合取范式\(\phi\)有n个变元和m个简单析取式。对一个文字，进行一次“化简”是指将\(x_i,\lnot x_i\)分别代入每一个析取式中，对单文字的析取式进行整理并递归化简，直到出现矛盾或所有余下的析取式都是二元的为止。如果两次化简都出现矛盾，则\(\phi\)不可满足；否则取一个成功的化简，重复上述流程。如果能清空所有析取式，则\(\phi\)可满足。
另证：构造一个有向图，有2n个顶点即为\(x_i , \lnot x_i.\) 对于简单析取式\(a\lor b,\)构造2条有向边\(\lnot a\to b,\lnot b \to a.\)断言：\(\phi\)是可满足的当且仅当图中不含有形如\(x\to \lnot x \)的路径。已知PATH问题是P类中的，对所有变元依次检查即可。

    所属分类：TCS     发表于2021-12-21