算法导论34.3 Exercises 答案

34.3-1

根据图34.8b的图，可以给出这个布尔组合电路所定义的布尔公式如下：

\[((x_1\lor x_2)\land (\neg(\neg x_3))) \land((\neg(\neg x_3))\lor(x_1\land(\neg x_3)\land x_2))\land (x_1\land(\neg x_3)\land x_2)\]

化简后，可以得到这个布尔公式为：

\[((x_1\lor x_2)\land x_3) \land( x_3\lor(x_1\land(\neg x_3)\land x_2))\land (x_1\land(\neg x_3)\land x_2)\]

去掉一部分括号，根据运算符\(\land\)的交换律及结合律，可以得到

\[(x_1\lor x_2) \land( x_3\lor(x_1\land(\neg x_3)\land x_2))\land x_1\land x_2\land x_3\land(\neg x_3)\]

由于\(x_3\land (\neg x_3)\)不可能为\(1\)，因此原来的布尔表达式的值必定为\(0\)，它是不可满足的。

34.3-2

如果\(L_1\le_P L_2\)，那么意味着存在一个规约函数\(f_1\)以及一个时间复杂度为\(O(n^{k_1})\)的算法\(F_1\)计算规约函数\(f_1\)，将语言\(L_1\)规约到\(L_2\)，其中\(k_1\)为一个正常数。同样的，如果\(L_2\le_P L_3\)，那么意味着存在一个规约函数\(f_2\)以及一个时间复杂度为\(O(n^{k_2})\)的算法\(F_2\)计算规约函数\(f_2\)，将语言\(L_2\)规约到\(L_3\)，其中\(k_2\)为一个正常数。

通过\(f_1\)和\(f_2\)，可以构造出规约函数\(f_3=f_2\circ f_1\)，并且存在算法\(F_3\)通过嵌套调用\(F_2,F_1\)计算规约函数\(f_3\)，将语言\(L_1\)规约成语言\(L_3\)，其时间复杂度为\(O(n^{k_1k_2})\)。因此有\(L_1\le_P L_3\)。

34.3-3

可见，由于充分性和必要性的过程互为补运算，证明过程是对称的。因此只需要证明一个方向即可。

这里证明充分性，\(L\le_P \overline{L}\)意味着存在一个规约函数\(f\)以及一个多项式时间的算法\(F\)计算规约函数\(f\)，将语言\(L\)规约到\(\overline{L}\)。

对于一个\(x\)，如果\(x\in\overline{L}\)，那么有\(x\not\in L\)，即\(f(x)\not\in \overline{L}\)，从而得到\(f(x)\in L\)。也就是说，\(f\)同样可以将语言\(\overline{L}\)规约到\(L\)，因此充分性成立。

必要性的证明过程相同，最终原结论成立。

34.3-4

相对于原来的检验算法\(A\)，新的检验算法\(A'\)接受的证书\(y\)只需要包含所有的电路输入即可，而不需要包含每一根线上的值。检测算法\(A'\)将会根据\(C\)的编码解析出原来的电路，然后按照给定\(y\)作为输入值，将整个布尔电路的所有导线的值计算出来。最终得到电路的输出结果，如果电路的输出结果为\(1\)，那么说明这个\(y\)是\(x\)是可满足的证据，算法\(A'\)返回\(1\)，否则返回\(0\)。

34.3-5

当使用图34-9来论证使用的工作存储器数量为\(n\)的多项式时，假设了存储单元是连续的。

实际上，这些存储空间不必是连续的，对于不同功能的内容（数据或代码），只需要在整个存储空间上划出一小部分足够让这些内容存储下来即可。由于这里仅仅是强调使用的存储器数量的上限，因此假设存储单元连续是不失一般性的。

34.3-6

可见\(\varnothing,\{0,1\}^{\ast}\in P\)。考虑使用反证法来证明\(\varnothing,\{0,1\}^{\ast}\)对\(P\)不是完全的。

现在假设\(\varnothing\)对\(P\)是完全的，由于\(\{0,1\}^{\ast}\in P\)，因此\(\{0,1\}^{\ast}\le_P \varnothing\)。那么必定存在多项式规约函数\(f\)，使得\(x\in \{0,1\}^{\ast}\)当且仅当\(f(x)\in \varnothing\)。但是\(f(x)\in\varnothing\)是永远不成立的，因为\(\varnothing\)是空集合，然而\(\{0,1\}^{\ast}\)并不是空集合，这引出了矛盾。因此\(\varnothing\)对\(P\)不是完全的。

现在假设\(\{0,1\}^{\ast}\)对\(P\)是完全的，由于\(\varnothing\in P\)，因此\(\varnothing\le _P \{0,1\}^{\ast}\)。和之前的类似，那么必定存在多项式规约函数\(f'\)，使得\(x\in \varnothing\)当且仅当\(f'(x)\in \{0,1\}^{\ast}\)。但是\(x\in\varnothing\)是永远不成立的，因为\(\varnothing\)是空集合，然而\(\{0,1\}^{\ast}\)并不是空集合，这引出了矛盾。因此\(\{0,1\}^{\ast}\)同样对\(P\)不是完全的。（注意：这个结论也可以从题目34.3-2中直接得出）

接下来考虑\(P\)中除\(\varnothing,\{0,1\}^{\ast}\)中的任意一个语言\(L\)，并假设任意语言\(L'\in P\)。取\(y_1\in L,y_2\in \overline{L}\)。由于\(L'\in P\)，因此必定存在一个算法\(A'\)可以在多项式时间内判断一个字符串\(x\)是否在语言\(L'\)。我们可以构造一个规约函数\(f\)：

\(f(x)= \left \{\begin{aligned} &y_1 & & \text{if}\quad x\in L' \\ &y_2 & & \text{if}\quad x\not\in L' \\ \end{aligned}\right.\)

并且可以构造出一个多项式时间算法\(F\)用于计算\(f\)，它是将\(A'\)作为子程序进行计算。因此可以得到\(L'\le_P L\)。

也就是说，\(\forall L'\in P,L'\le_P L\)均成立，因此\(L\)对\(P\)是完全的。\(\varnothing,\{0,1\}^{\ast}\)是在\(P\)中仅有两个语言对\(P\)是不完全的。

34.3-7

和题目一样，由于充分性和必要性的过程互为补运算，证明过程是对称的。因此只需要证明一个方向即可。

充分性：由于\(L\)对\(\text{NP}\)是完全的，因此\(L\in\text{NP}\)，这意味着\(\overline{L}\in\text{co-NP}\)。类似的，由于\(\forall L'\in \text{NP}\)，都有\(L'\le_PL\)。这说明存在一个规约函数\(f\)和一个多项式算法\(F\)用来计算\(f\)，将\(L'\)归约到\(L\)中。按照\(f\)的定义，可见\(x\in L'\)当且仅当\(f(x)\in L\)。也就是说\(x\in \overline{L'}\)当且仅当\(x\in\overline{L}\)。因此多项式算法\(F\)也可以将\(\overline{L'}\)在多项式时间内归约到\(\overline{L}\)，即\(\overline{L'}\le_P\overline{L}\)。因此\(\overline{L}\)对\(\text{co-NP}\)是完全的。

必要性的证明过程相同，最终原结论成立。

34.3-8

需要注意的是，证明一个语言\(L\)是NP困难的，只需要证明\(\forall L'\in\text{NP}\)，将\(L'\)归约到\(L\)的多项式规约函数\(f\)存在即可，而并不需要显式地构造一个多项式算法\(F\)来计算\(f\)。证明的内容相当于是，由于多项式规约函数\(f\)存在，因此在多项式时间内计算规约函数\(f\)的算法\(F\)也存在。因此，由于\(L'\in \text{NP}\)，都有一个多项式算法\(A'\)来对\(L'\)进行验证。多项式算法\(A'\)存在，那么调用\(A'\)来计算\(f\)的算法\(F\)也是存在的，它是多项式次数的。因此，哪怕不需要知道\(O(n^k)\)的常数，也是足够用来证明CIRCUIT-SAT是NP困难的。