算法导论 34 章习题

在学校学 whk 的空闲~

\(\bold{34.1}\)

\(\bold{34.1-1}\) 若 \(\operatorname{LONGEST-PATH-LENGTH}\) 可以在多项式时间内解决，那么只需调用它并将其答案与给定的 \(k\) 比较即可，故 \(\operatorname{LONGEST-PATH}\in\operatorname{P}\)；反过来若 \(\operatorname{LONGEST-PATH}\in\operatorname{P}\)，由于 \(\operatorname{LONGEST-PATH-LENGTH}\) 所优化的值有界 \(|V|=\Omega(\sqrt{n})\) 且多项式在乘法运算下封闭，故将该判定问题的算法转化为解决最优化问题的算法后仍然是多项式时间的。

\(\bold{34.1-2}\) 其为建立在实例集合 \(I\) 和解集合 \(S\) 上的一个二元关系，\(I\) 中的元素为所有无向图 \(G\)，\(S\) 中元素为顶点序列 \(\langle v_1,v_2,\dots,v_n\rangle\)。

给定无向图 \(G\) 及一个整数 \(k\)，判定 \(G\) 中是否存在一个长度不小于 \(k\) 的简单回路。

\(L=\{\langle G,k\rangle|\) \(G=(V,E)\) 是一个无向图，\(k\) 为一个整数，\(G\) 中存在一条长度不小于 \(k\) 的简单回路
\(\}\)。

\(\bold{34.1-3}\) 给定图 \(G=(V,E)\)，用长度为 \(|V|^2\) 的串 \(b\) 来编码邻接矩阵，\(b_{(u-1)|V|+v}\) 表示 \(G_{u,v}\)。对于邻接表，用长度为一个常数 \(c=O(\lg|V|)\)
的串来表示一个整数，然后从点 \(1\) 开始向编码末端逐个加入点的链表，首先加入链表大小 \(s_i\)，接下来 \(s_i\) 个整数表示链表中的所有元素，总长度 \(O(c\sum_{u\in V}(s_u+1))=O((|V|+|E|)\lg|V|)\)。

如果我们已知 \(G\) 则根据上面编码的过程是多项式时间的，同时我们也能在多项式时间内输入其中一种编码来得知 \(G\)，故他们之间的转换可以做到多项式时间，即它们是多项式相关的。

\(\bold{34.1-4}\) 不是。

它的输入有 \(2n+2=O(n)\) 个整数 \(n,W,v_1,v_2,\dots,v_n,w_1,w_2,\dots,w_n\)。设这些的整数的长度都为 \(O(k)\)，则输入规模为 \(O(nk)\)，且有 \(W=O(2^k)\)，这个算法的复杂度 \(O(nW)=O(n2^k)\) 和输入规模中的 \(k\) 呈超多项式关系，故它不是一个多项式算法。

\(\bold{34.1-5}\) 设输入规模为 \(n\)，\(f(n)\) 为对子例程进行调用的次数，子例程是一个 \(O(n^q)\) 的多项式时间算法。

我们构造一个这样的算法 \(A\)：将输入作为第一次子例程调用的输入，将这个子例程的输出作为第二次子例程调用的输入，如此进行 \(f(n)\) 次。第一次的输入规模为 \(n\)，由于其时间为 \(O(n^q)\) 故输出规模也是 \(O(n^q)\) 的，这样的话第二次输入的规模就变为 \(O(n^q)\)，输出规模为 \(O(n^{q^2})\)，进行 \(f(n)\) 次调用后的输出规模为 \(O(n^{q^{f(n)}})\)，若 \(f(n)=O(n^w)\) 那么其输出规模就是指数规模的了，其运行时间总是不小于输出规模，故它是指数时间的。

\(\bold{34.1-6}\) 并集，交集的封闭性是显然的。

对于连结 \(L'=L_1L_2(L_1,L_2\in\operatorname{P})\)，构造算法 \(B\) 来判定 \(L'\)，由于 \(L_1,L_2\in\operatorname{P}\)，存在多项式时间算法 \(A_1,A_2\) 判定 \(L_1,L_2\)，对于输入 \(x\) 我们将其从中间某位置分成左右两个子串 \(x_l,x_r\)，\(B(x)=1\) 当且仅当存在一种分割方案使得 \(A_1(x_l)=A_2(x_r)=1\)。

首先说明 \(B\) 是多项式时间的，设 \(|x|=n\)，总分割方式是 \(O(n)\) 的，每一种分割都要调用一次 \(A_1,A_2\)，组合起来显然也是多项式时间的。

接下来说明 \(B\) 可以判定 \(L'\)。若 \(x\in L\) 则 \(x=x_lx_r\) 其中 \(x_l\in L_1,x_r\in L_2\)，即 \(A_1(x_l)=A_2(x_r)=1\)，由于每一种分割都会被判定，这一种也不例外，故 \(B(x)=1\)；反过来，若 \(B(x)=1\)，则意味着对 \(x\) 我们找到了一种分割 \(x=x_lx_r\) 满足 \(A_1(x_l)=A_2(x_r)=1\) 即 \(x_l\in L_1\)，\(x_r\in L_2\)，由连结的定义知 \(x=x_lx_r\in L'\)。综上两方面，\(L'\in\operatorname{P}\)，即 \(\operatorname{P}\) 在连结运算下是封闭的。

对于 \(\operatorname{Kleene}\) 星 \(L^*=\{\varepsilon\}\cup L\cup L^2\cup\cdots(L\in\operatorname{P})\)，可以直接由连结和并集的封闭性得到其封闭性。

对于补集 \(\overline{L}=\Sigma^*-L(L\in\operatorname{P})\)，构造算法 \(B\) 来判定 \(\overline{L}\)，首先由于 \(L\in\operatorname{P}\)，存在多项式时间算法 \(A\) 判定 \(L\)，对于输入串 \(x\)，\(B(x)=0\) 当且仅当 \(A(x)=1\)。正确性比较显然（懒得写了

\(\bold{34.2}\)

规定下面所有的图都是用邻接矩阵表示进行编码。

\(\bold{34.2-1}\) 证书 \(y\) 是一个双射 \(f:V_1\rightarrow V_2\) 及其反函数 \(f^{-1}\)，对于输入 \(x=\langle G_1,G_2\rangle\)，若对于所有 \((u,v)\in E_1\) 都有 \((f(u),f(v))\in E_2\) 及对于所有 \((u,v)\in E_2\) 都有 \((f^{-1}(u),f^{-1}(v))\in E_1\)，那么 \(A(x)=1\)，否则 \(A(x)=0\)。这个验证可以在 \(O(|E_1|+|E_2|)=O(|V_1|^2+|V_2|^2)=O(n)\) 时间内进行，这个检验过程就是同构图的定义故它的正确性也是显然的，推得 \(\operatorname{GRAPH-ISOMORPHISM}\in\operatorname{NP}\)。

\(\bold{34.2-2}\) 假设其为哈密顿图，将其中的哈密顿回路拿出来，这个圈上的任意相邻顶点所属左右不相同且有奇数个顶点，这是不可能的。

\(\bold{34.2-3}\) 新建一个图 \(G'\) 并初始化为 \(G\)，依次检查每个 \(e\in E\)，若 \(\operatorname{HAM-CYCLE}(\langle G''=(V,E'-\{e\}\rangle)=1\)，则 \(E'\rightarrow E'-\{e\}\)，否则保留这条边。检查次数为 \(O(|E|)=O(n)\)，组合 \(\operatorname{HAM-CYCLE}\) 后也是多项式时间的。

\(\bold{34.2-4}\) 同 \(\text{34.1-6}\)，只是枚举分割时要同时枚举 \(x\) 和 \(y\) 的分割。

\(\bold{34.2-5}\) 考虑枚举证书 \(y\)。我们找一个足够大的常数 \(k\) 对于所有的语言 \(L\in\operatorname{NP}\)，都存在一个多项式算法 \(A\) 以及一个隐含的常数 \(c\)，使得对于任意 \(x\in L\) 都存在证书 \(y\) 满足 \(|y|\leq c|x|^k\) 使得 \(A(x,y)=1\)。我们以此为基础构造算法 \(B\) 来验证 \(L\)，设输入规模 \(|x|=n\)，枚举所有的长度不大于 \(cn^k\) 的 \(01\) 串 \(y\) 并计算 \(A(x,y)\)，若存在 \(y\) 使得 \(A(x,y)=1\) 则 \(B(x)=1\)，否则 \(B(x)=0\)。花费时间 \(2^{cn^k}\cdot O(n^q)=2^{O(n^k)}\)。

\(\bold{34.2-6}\) 显然可以将哈密顿路径作为证书来进行多项式时间的验证。

\(\bold{34.2-7}\) 在 \(\text{DAG}\) \(G=(V,E)\) 中的 \(u,v\) 间存在哈密顿路径，当且仅当对 \(G\) 进行拓扑排序后的顶点序列 \(\langle v_1,v_2,\dots,v_k\rangle\) 中有 \(v_1=u,v_k=v\) 且 \((v_i,v_{i+1})\in E\ (1\leq i\leq |V|)\)。时间复杂度 \(O(|V|+|E|)=O(n)\)。

\(\bold{34.2-8}\) 其补为 \(\overline{\operatorname{TAUTOLOGY}}=\{\langle\phi\rangle|\) 存在一种对于 \(\phi\) 中变量的赋值使得其值为 \(0\) \(\}\)。定义证书为一组变量的赋值 \(\langle x_1,x_2,\dots,x_k\rangle\)，在多项式时间内验证是很容易的。

\(\bold{34.2-9}\) 由于 \(\operatorname{P}\subseteq \operatorname{NP}\)，且 \(\operatorname{P}\) 在补运算下封闭，故对于所有 \(L\in \operatorname{P}\) 有 \(\overline{L}\in P\) 即 \(\overline{L}\in\operatorname{NP}\)，根据 \(\operatorname{co-NP}\) 的定义有 \(L\in\operatorname{co-NP}\)，即 \(\operatorname{P}\subseteq\operatorname{co-NP}\)。

\(\bold{34.2-10}\) 假设 \(\operatorname{P}=\operatorname{NP}\)，故 \(\operatorname{P}=\operatorname{NP}\subseteq \operatorname{co-NP}\)，由于 \(\operatorname{NP}\neq\operatorname{co-NP}\) 必定存在某种语言 \(L\in \operatorname{co-NP}-\operatorname{NP}\)，根据 \(\operatorname{co-NP}\) 定义，它的补 \(\overline{L}\in \operatorname{NP}\) 继而得到 \(\overline{L}\in \operatorname{co-NP}\)，这也就意味着 \(\overline{L}\) 的补 \(L\in\operatorname{NP}\)，与 \(L\in\operatorname{co-NP}-\operatorname{NP}\) 矛盾。故假设不成立即 \(\operatorname{P}\neq\operatorname{NP}\)。

\(\bold{34.2-11}\) 好像不太会啊 qwq

\(\bold{34.3}\)

\(\bold{34.3-1}\) 显然！

\(\bold{34.3-2}\) 规约两次来说明 \(L_1\leq_{\operatorname{P}}L_3\)。

\(\bold{34.3-3}\) 规约函数 \(f\) 将 \(L_1\) 规约至 \(\overline{L}\) 即 \(x\in L_1\Leftrightarrow f(x)\in\overline{L}\)，换句话说即 \(x\in\overline{L_1}\Leftrightarrow f(x)\in L\)，也就是说 \(f\) 将 \(L_1\) 规约至 \(\overline{L}\) 的同时也将 \(\overline{L_1}\) 规约至了 \(L\)，反向是对称的，亦然。

一般地有 \(L_1\leq_{\operatorname{P}}L_2\Leftrightarrow \overline{L_1}\leq_{\operatorname{P}}\overline{L_2}\)。