计算复杂性第十章——复杂性高级专题

$\quad$ 本章主要内容包括近似算法、概率算法、交互式证明系统、并行计算和密码学。

一、近似算法

$\quad$ 某些NPC问题我们可以用多项式时间得到其近似解。例如最小顶点覆盖问题，我们就可以用如下算法得到一个2倍近似的解：对于图G，我们重复以下操作直至G中所有的边都与标记的边相邻：1.在G中找出一条不与任何有标记的边相邻的边；2.给这条边做上标记。最后输出所有标记的边的顶点即可。
$\quad$ 上述算法给出的顶点覆盖的规模不超过最小顶点覆盖的2倍，证明如下：

1.记H是有标记的边的集合，X是输出的顶点集合，Y是最小顶点覆盖的集合。
2.G中每一条边要么属于H，要么与H中某条边相邻，故X是G的一个顶点覆盖。
3.接着证明X中顶点的数目大小是H的2倍且H不大于Y，这样就能得到结论。关键在于证明H不大于Y：H中每一条边都与Y中某个顶点关联，而Y中可能存在某两个顶点关联一条边，故而 $|H|\le |Y|$ 。得证。

$\quad$ 如果一个最小化问题的近似算法总能找到不超过最优解 $k$ 倍的可行解，则称这个算法是 $k-优$ 的；对于最大化问题，一个 $k-优$ 近似算法总能找到不小于最优解大小的 $\frac{1}{k}$ 的可行解。
$\quad$ 把图G的顶点集V划分为两个互不相交的子集S和T，称为图G的割。其中一个顶点在S，另一个顶点在T中的边称为割边，割边的数目称为割的大小。因此最大割就是寻找一种顶点划分方式，使得割边数目最多。接下来给出最大割问题的近似算法：1.令 $S={},T=V$ ;2.如果把一个顶点从S移动到T或者从T移动到S，使割大小变大，则做这样的移动，且重复这一步；3.如果不存在这样的顶点，则输出当前的割并停止。
$\quad$ 上述算法是 $2-优$ 的多项式时间近似算法。
证明：割的大小不超过G的边数，因此证明上述算法输出的割大小至少包含G中所有边的一半，即证明通过上述算法得到的割边数目大于非割边数目即可。这是显然的，算法的第二步保证了这一点，如果割边数目少于非割边数目，那么就能通过算法第二步调整。

二、概率算法

BPP类

$\quad$ 为了介绍概率计算问题，定义一个新的计算模型——概率图灵机。概率图灵机M是一种非确定型图灵机，它的每一非确定步称作掷硬币步，并且有两个合法的下步动作。按照下述方式把概率赋给M对输入w的每一个计算分支b，定义分支b的概率为 $Pr[b]=2^{-k}$ ，k是在分支b中出现的掷硬币的步数，定义M接受w的概率为 $Pr[M接受w]=\sum_{b是接受分支}Pr[b]$ ，显然 $Pr[M拒绝w]=1-Pr[M接受w]$ 。
$\quad$ 通常，当概率图灵机接受属于某一语言的所有字符串并且拒绝不在这个语言中的左右字符串时称概率图灵机判定该语言。如果允许机器有小的错误概率，对于某个小正数 $\epsilon$ ，如果：

1. $w\in A$ 蕴含 $Pr[M接受w]\geq 1-\epsilon$
2.1. $w\notin A$ 蕴含 $Pr[M拒绝w]\geq 1-\epsilon$
则称M以 $\epsilon$ 的错误概率判定语言A。错误概率的边界依赖于输入串的长度 $n$ ，例如，错误概率 $2^{-n}$ 表示指数地小的错误概率。

$\quad$ 定义：BPP是多项式时间的概率图灵机以错误概率 $\frac{1}{3}$ 判定的语言类。
$\quad$ 引理：设 $M_1是错误概率为\epsilon(0<\epsilon<1/2)$ 的多项式概率图灵机，则给定任意多项式 $p(n)$ ，存在与M1等价的错误概率为 $2^{-p(n)}$ 的多项式时间概率图灵机M2。

素数性

$\quad$ 这里给出一个简单的检验一个数是素数还是合数的多项式时间概率算法。
$\quad$ 基础： $x\equiv y(mod p)$ 表示x和y模p后相等。
$\quad$ 费马小定理：如果p是素数，且 $a\in \{1,\cdots,p-1\}，则a^{p-1}\equiv 1(mod p)$ 。
$\quad$ 能否根据费马小定理给出素数的判定算法，即如果 $a\in \{1,\cdots,p-1\}，且对于所有a，满足a^{p-1}\equiv 1(mod p)$ ，那么 $p$ 是素数。几乎可以，只有极少数卡米切尔数不满足，除此之外都满足。事实上，满足上述判定条件的数称为伪素数。这里不加证明的给出一个定理：如果一个数不是伪素数，那么它至少不能通过全部费马测试的一半。算法随机的进行若干次测试，若有一次测试没通过，则该数一定是合数。算法含有一个用来确定错误概率的参数 $k$ ：
对于输入p:

1.在 $Zp^+=\{1,2,\cdots,p-1\}中随机的a_1,a_2,\cdots,a_k$
2.对于每一个 $i$ ，计算 $a_i^{p-1}mod p$
3.如果所有计算值都等于1，则接受，否则拒绝。

这样，一个合数通过全部k个随机测试的概率不大于 $2^{-k}$ 。
$\quad$ 为了避免卡米切尔数带来的问题，我们进一步优化上述算法来解决伪素数的问题，这样，我们的算法就是最大错误概率为 $2^{-k}$ 的素数判定算法：
计算复杂性第十章——复杂性高级专题
$\quad$ 上述算法的正确性证明依赖于下面引理：

1.如果p是偶数，显然成立
2.如果p是奇素数，则 $Pr[PRIME接受p]=1$
3.如果p是奇合数，则 $Pr[PRIME接受p]\le 2^{-k}$

该素数性概率算法 $\in BPP$ ，具有单侧错误，但算法输出拒绝时一定是合数；但接受时可能时素数或者合数。对于这个复杂性类我们专门定义为RP：RP是多项式概率图灵机识别的语言类，在这里，在语言中的输入以不小于 $\frac{1}{2}$ 的概率被接受，不在语言中的输入以概率1被拒绝。

只读一次的分支程序

$\quad$ 分支程序是一个有向无环图，除了两个输出顶点被标记为0或1外，它的所有顶点都被标记为变量，这类顶点为查询顶点。每一个查询顶点引出两条边，一条标记为0，另一条为1，两个输出顶点没有引出的边。在分支程序中指定一个顶点为起始顶点。

三、交互式证明系统

$\quad$ 在SAT问题的补中，证明者可以提供一个赋值使得多项式时间的验证者相信公式 $\phi$ 是不可满足的。证明者能类似的使验证者相信一个公式使不可满足的吗？由于不知道SAT在NP中的补，因此不能依赖上述证明思路。通过以下构造：允许证明者和验证者双向通话；其次，检验者是一台多项时间的概率图灵机，它以很大把握做出正确的回答。这样的一对证明者和检验者构成一个交互式证明系统。
$\quad$ 图的非同构。同构(ISO)：如果两个图通过调整它们的顶点顺序使得其相同，则这两个图同构。ISO属于NP，但目前不能证明它是否是NPC的，这是极少数在NP中尚未明确位置的一个问题（因式分解问题也是这样的）。这次考虑其补问题，即 $NOISO=\{<G,H>|G,H是两个不同构的图\}$ ，算法如下：
计算复杂性第十章——复杂性高级专题

模型定义

$\quad$ 为了形式地定义交互式证明系统，描述检验者、验证者及其相互作用。定义检验者是一个函数V，它根据至今传递的信息历史，计算下一次传送给证明者的信息，V有三个输入：

1.输入串，我们的目标是确定这个字符串是否是某个语言的成员。
2.随即输入，给检验者提供一个随机选取的输入串，用来代替在计算中做概率动作的能力。
3.部分信息历史

证明者有两个输入：输入串和部分信息历史。
计算复杂性第十章——复杂性高级专题

IP=PSPACE

$\quad$ IP包含NP类和BPP类。IP=PSPACE，于是，对于PSPACE中的任一语言，证明者能够使多项式时间的概率检验者相信该语言中字符串的成员资格。