算法导论34.4 Exercises 答案

34.4-1

可以构造的电路形式如下，如图是一个$n=3$规模的电路：

可见，第$k(k\ge 1)$层的电路的输出端所代表的表达式，就包含了$2^k-1$个运算符，因此这个电路一共有$n$层时，整个电路的输出端一共有$2^{n+1}-1$个运算符，即这个表达式的长度是指数增长的。

34.4-2

对于$\phi’$中的所有子句，经过3个步骤后可以得到：

$\begin{aligned}
\phi_0’’’&=y&&=(y \lor p \lor q) \land (y \lor p \lor \neg q) \land (y \lor \neg p \lor q) \land (y \lor \neg p \lor \neg q)\
\phi_1’’’&=(y_1 \leftrightarrow (y_2 \land \neg x_2)) &&= (\neg y_1 \lor \neg y_2 \lor \neg x_2) \land (\neg y_1 \lor y_2 \lor \neg x_2) \land (\neg y_1 \lor y_2 \lor x_2) \land (y_1 \lor \neg y_2 \lor x_2)\
\phi_2’’’&=(y_2 \leftrightarrow (y_3 \lor y_4)) &&= (\neg y_2 \lor y_3 \lor y_4) \land (y_2 \lor \neg y_3 \lor \neg y_4) \land (y_2 \lor \neg y_3 \lor y_4) \land (y_2 \lor y_3 \lor \neg y_4)\
\phi_3’’’&=(y_3 \leftrightarrow (x_1 \rightarrow x_2)) &&= (\neg y_3 \lor \neg x_2 \lor x_2) \land (y_3 \lor \neg x_1 \lor \neg x_2) \land (y_1 \lor x_1 \lor \neg x_2) \land (y_3 \lor x_1 \lor x_2)\
\phi_4’’’&=(y_4 \leftrightarrow \neg y_5) &&= (\neg x_4 \lor \neg y_5 \lor q) \land (\neg x_4 \lor \neg y_5 \lor \neg p) \land (x_4 \lor y_5 \lor p) \land (x_4 \lor y_5 \lor \neg p)\
\phi_5’’’&=(y_5 \leftrightarrow (y_6 \lor x_4)) &&= (\neg y_5 \lor y_6 \lor x_4) \land (y_5 \lor \neg y_6 \lor \neg x_4) \land (y_5 \lor \neg y_6 \lor x_4) \land (y_5 \lor y_6 \lor \neg x_4)\
\phi_6’’’&=(y_6 \leftrightarrow (\neg x_1 \leftrightarrow x_3)) &&= (\neg y_6 \lor \neg x_1 \lor \neg x_3) \land (\neg y_6 \lor x_1 \lor x_3) \land (y_6 \lor \neg x_1 \lor x_3) \land (y_6 \lor x_1 \lor \neg x_3)
\end{aligned}$

因此最终$\phi$转化后得到$3\text{-CNF}$的表达式$\phi’’’$为：

$\begin{aligned}
\phi’’’=&(y \lor p \lor q) \land (y \lor p \lor \neg q) \land (y \lor \neg p \lor q) \land (y \lor \neg p \lor \neg q)\land\
&(\neg y_1 \lor \neg y_2 \lor \neg x_2) \land (\neg y_1 \lor y_2 \lor \neg x_2) \land (\neg y_1 \lor y_2 \lor x_2) \land (y_1 \lor \neg y_2 \lor x_2)\land\
&(\neg y_2 \lor y_3 \lor y_4) \land (y_2 \lor \neg y_3 \lor \neg y_4) \land (y_2 \lor \neg y_3 \lor y_4) \land (y_2 \lor y_3 \lor \neg y_4)\land\
&(\neg y_3 \lor \neg x_2 \lor x_2) \land (y_3 \lor \neg x_1 \lor \neg x_2) \land (y_1 \lor x_1 \lor \neg x_2) \land (y_3 \lor x_1 \lor x_2)\land\
&(\neg x_4 \lor \neg y_5 \lor q) \land (\neg x_4 \lor \neg y_5 \lor \neg p) \land (x_4 \lor y_5 \lor p) \land (x_4 \lor y_5 \lor \neg p)\land\
&(\neg y_5 \lor y_6 \lor x_4) \land (y_5 \lor \neg y_6 \lor \neg x_4) \land (y_5 \lor \neg y_6 \lor x_4) \land (y_5 \lor y_6 \lor \neg x_4)\land\
&(\neg y_6 \lor \neg x_1 \lor \neg x_3) \land (\neg y_6 \lor x_1 \lor x_3) \land (y_6 \lor \neg x_1 \lor x_3) \land (y_6 \lor x_1 \lor \neg x_3)
\end{aligned}$

34.4-3

这种策略是错误的。如果$\phi$有$n$个自由布尔变量，那么构造出的真值表一共有$2^n$项，从这个真值表导出的表达式的长度至少是$\Omega(2^n)$的，而不是多项式长度的。因此原结论错误。

34.4-4

根据题目34.3-7的结论，为了证明语言$L=\text{TAUTOLOGY}$对$\text{co-NP}$是完全的，只需要证明$\overline{L}$是NP完全的即可，其中$\overline{L}$是如下布尔表达式$\phi$所表示的集合：存在一组输入变量，使得这个表达式的输出值为$0$。

首先证明$\overline{L}\in \text{NP}$。证明过程非常简单：验证算法可以在多项式时间内对一个表达式$\phi$和一组输入$x$，判断出表达式的输出值是否为$0$。这个步骤和定理34.9对应步骤的证明是一样的，因此$\overline{L}\in\text{NP}$。（也可以从题目34.2-8直接得出此结论。）

接下来证明$\overline{L}$是NP困难的。根据定理34.9得知，问题$\text{SAT}$是NP完全的。因此，通过证明$\text{SAT}\le_P \overline{L}$，从而完成此证明。对于问题$\text{SAT}$中的任意一个表达式$\phi$，存在一组输入$x$使得$\phi$的输出为$0$。规约函数$f$则是将表达式$\phi$进行取反，即$f(\phi)=\neg\phi$，它可以在多项式时间内被计算出来。因此有$\text{SAT}\le_P\overline{L}$，也就是说，$\overline{L}$是NP困难的。

因此，$\overline{L}$是NP完全的，原来的结论成立。

34.4-5

对于一个析取范式$\phi$，它是表示为所有子句的或，并且每个子句都是多个文字的与。因此每个子句$\phi_i$和$\phi$之间的关系可以写成

$$\phi=\bigvee_{i=1}^k \phi_i$$

因此，对于一个析取范式的可满足性问题，只要其中一个子句的值为$1$，那么整个$\phi$的输出值为$1$。我们可以枚举每个子句$\phi_i$。由于$\phi$是一系列文字的与运算，只要$\phi_i$有一个输入为$1$即可满足要求。检查$\phi_i$中的所有文字，如果不存布尔变量$x_j$，使得$x_j$和$\neg x_j$都在这个子句中，子句$\phi_i$的值就可以为$1$。只要将在子句$\phi_i$中，没有取反$\neg$的变量赋予$1$，带有取反符号的赋予$0$即可，最终这是一个证明该析取范式是可满足的证据。如果$\phi$每一个子句，都有某个布尔变量$x_j$和$\neg x_j$都在这个子句中，那么$\phi$是不可满足的。每个子句只需要线性的时间即可完成判断。

因此，判断析取范式的可行性问题$\text{DNF-SAT}\in P$，原结论成立。

34.4-6

如果存在一个多项式算法DECIDE-FORMULA-SATISFIABILITY用于判断布尔表达式的可满足性。那么考虑如下程序FIND-SATISFYING-ASSIGNMENT用于为每个布尔变量赋值。

//A是某个布尔表达式，X是自由变量集合
//DECIDE-FORMULA-SATISFIABILITY(P, X)用于检测布尔表达式P是否具有可行性，X是其布尔变量集合。
FIND-SATISFYING-ASSIGNMENT(P, X)
  X' = ∅
  while X != ∅
    select x from X randomly and remove it
    X = X - {x}
    X' = X' ∪ {x}
    all x in P are assigned a value of 1
    simplify P to get a new expression P'
    if DECIDE-FORMULA-SATISFIABILITY(P', X) == 1
      x.value = 1
      P = P'
    else
      x.value = 0
      all x in P are assigned a value of 0
      simplify P to get a new expression P'
      P = P'
  return X'

FIND-SATISFYING-ASSIGNMENT的基本思想是，对每个变量尝试进行$x_i$赋值，如果赋予其中一个值后（程序中是$1$），对于剩下的变量来说，这个布尔表达式是可满足的，那么当前赋值是正确的，否则赋予另外一个值（程序中是$0$）。

所有化简过程都可以在多项式时间内完成。上面的算法中，如果布尔表达式包含了$n$个自由变量，那么FIND-SATISFYING-ASSIGNMENT只会调用$n$次DECIDE-FORMULA-SATISFIABILITY，并且每次调用的规模都不大于原来的布尔表达式的长度。由于DECIDE-FORMULA-SATISFIABILITY是多项式时间的算法，因此FIND-SATISFYING-ASSIGNMENT也是多项式时间的算法，原结论成立。

34.4-7

假设这个恰有两个文字的合取范式$\phi$被表示成$\displaystyle{\phi=\bigwedge_{i=1}^n y_i\lor z_i}$，其中$y_i,z_i$是第$i$个子句的文字$\phi_i$，一共有$k$个自由变量。考虑有向图$G=(V,E)$，其中$V={x_1,\neg x_1,x_2,\neg x_2,\dots,x_k,\neg x_k}$，即表示这$k$个自由变量可能的$2k$个文字。

对于每个子句$\phi_i$，将边$(\neg y_i,z_i),(\neg y_i,z_i)$添加到$E$中。原因是，如果$y_i$和$z_i$其中一个被赋予$0$，那么另一个变量就必须赋予$1$。

接下来对图$G$运行章节20.5所描述的求解强连通算法STRONGLY-CONNECTED-COMPONENTS。如果存在某个$i\in[1,k]$，使得$x_i,\neg x_i$都在一个强连通分量中，那么说明$x_i$对其中一个变量赋值都会导致$x_i$将会对另外一个变量进行赋值，这是不可能的，因此$\phi$此时不可满足。否则$\phi$是可满足的。

由于建立整个图$G$只需要花费$O(n)$的时间，并且算法STRONGLY-CONNECTED-COMPONENTS的时间复杂度为$O(E+V)$，因此恰好$2$个子句的可满足行问题是多项式时间内可判定的，即$\text{2-CNF-SAT}\in P$。