AADS Assignment4 idea
==

[TOC]

### 34.2-5
A language L is decided by an algorithm A if x $\in$ L entails A(x)=1 and x $\notin$ L entails A(x)=0.
So we can know that A language L belongs to NP if and only if there exists a two-input polynomial time algorithm A and a constant c such that L={x$\in${0,1}^*:there exists a certificate y with \|y\| = O(\|x\|^c) such that A(x,y)=1}

From this obersvation we can see that for each language L in NP, there is algorithm A that can verify each item x in L in polynomial time, given a certificate y with O(\|x\|^c).

Since the verification process can be completed in polynomial time, this means that the time Complexity of the algorithm is O(\|n\|^k) for some constant k.

为了检查是否存在一个certificate y，我们需要检查所有y的可能并分析A(x,y),其中\|y\|=O(\|x\|^c).在分析了2^\|y\|种certificates后，我们可以确定是否存在一个certificate y使得A(x,y)=1.

Therefore, there exists an algorithm A that decides any language in NP in 2^{O(n^k)} with constant k.

### 34.2-6
We suppose that there exits an algorithm which can decide whether the sequence c of Graph G is a HAM-path. So we check the path c from start point to end point to make sure each vertex appear only once and each edge belgons to E. We need polynimal time to check it, so HAM-path is a NP problem.

### 34.2-8
Let $\phi$ be a boolean formula constructed from the boolean input variables $x_1, x_2, \dots, x_k$, negations ($\neg$), ANDs ($\land$), ORs ($\lor$), and parentheses. The formula $\phi$ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables. Define TAUTOLOGY as the language of boolean formulas that are tautologies.
Show that TAUTOLOGY 2 co-NP.


思路：根据 $\text{co-NP}$ 问题的定义，
要证明: $\text{TAUTOLOGY}\in \text{co-NP}$
只需证明: $\overline{\text{TAUTOLOGY}} \in \text{NP}$
即可。

而根据题目信息可知 $\text{TAUTOLOGY}$ 的补集应该是如下描述：
设 $\phi$ 为一个布尔公式，它由布尔输入变量 $x_1, x_2, \dots, x_k$、非($\neg$)、AND($\land$)、OR($\lor$)和括号组成。对于公式的输入变量的每一种1和0赋值，存在布尔公式的结果为0。

对于上述问题：
在多项式时间内（$O(k+\text{逻辑运算次数})$）必定能判断赋值后布尔表达式的值为0，因此其是一个NP问题。

因此$\overline{\text{TAUTOLOGY}} \in \text{NP}$，
$\text{TAUTOLOGY}\in \text{co-NP}$。

### 34.3-2
由于 $L_1\leq_p L_2$ 所以有 $x \in L_1 \text{if and only if} f_1(x) \in L_2$. 同样 $L_2 \leq_p L_3$ 所以$x \in L_2 \text{if and
only if} f_2(x) \in L_3$.我们定义⼀个 $f_3$ 等于 $f_1of_2$， 因此 $x \in L_1 \text{if and only if} f_2(f_1(x)) \in L_3$
所以得到 $L_1 \leq_p L_3$ 因此得证。

### 34.4-6
**Step1：分解问题，定义问题**
首先用F来表示题目所给的polynomial boolean函数，定义当输入x是satisfiable formula返回 1，否则返回 0；
用 G 来 表 示 题 目 后 半 部 分 所 需 要 的 在 polynomial 时 间 复 杂 度 内 找 到 satisfying assignments（记为 SA）的方法函数；
也就是说，我们需要给出用 F 实现 G 的方法描述
假设我们最后找到的 satisfiable formula 的布尔变量由 $x_1, x_2, \dots, x_m$ 组成。

**Step2: 降解问题**
总体采用的是递归思路
首先，假设变量 $x_1$ 为 1，得到新的输入 formula y；（\*）
G 通过调用 F(y)在 polynomial 的时间里给出满足或不满足的结果（此时先不用在意 $x_2$ 到 $x_m$ 这些，因为用的是递归方法）以下作分类讨论：
如果满足，说明后部分 $x_2$ 到 $x_n$ 这些布尔变量能为 y 构成一个 SA，则对后部分的变量进行递
归，重复调用 F，参数设置变化参照（\*），即设 $x_2$ 为 1；
如果不满足，说明 $x_1$ 必须设为 0，这样后部分才能为 y 构成 SA，进行递归，参照（\*），唯一区别是把 $x_1$ 设为 0，$x_2$ 则首先设为 1 进行判断；
以上分类讨论的实质就是推断第一个值，实际上就是同一种递归多个条件判断；
这样最终就能得到 SA

**Step3：验证时间复杂度**
题目要求 G 保持 polynomial 复杂度，所以需要进行验证；
当只有一个布尔变量时，实际上只需调用两次 F 判断，显然 polynomial 不变；
当变量更多时，根据递归的性质，总复杂度=上一个递归层的复杂度+F 的复杂度（每次递归
通过 F 来判断 formula 满足与否），对 m 个布尔变量调用 m 层递归，也就是说最终复杂度是在原始复杂度前乘上一个不会超过 n 的因数，故最终时间复杂度依然是 polynomial。

### 34.5-1
**The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and it asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.**

**子图同构问题取两个无向图 G1 和 G2, 要回答 G1 是否与 G2 的一个子图同构这一问题。证明：子图同构问题是 NP 完全的。**

Prove $SIP \in NP$
The certificate $C$ is a permutation of $[1, . . . , n]$, we need to check:
$|V_1| = |V_2|$
$|E_1| = |E_2|$
for each pair of nodes $u_i, v_i \in V_1: (u_{c_{u_i}}, v_{c_{v_i}}) \in E_2 \text{if} (u_i, v_i) \in E_1$
for each pair of nodes $u_i, v_i \in V_1: (u_{c_{u_i}}, v_{c_{v_i}}) \notin E_2 \text{if} (u_i, v_i) \notin E_1$
It takes $O(|V_1|^2)$ time to verify the certificate, therefore subgraph-isomorphism problem $\in NP$.

Prove $SIP \in NPC$ by proving $CLIQUE \leq_P SIP$
Construction:
使用 Karp 规约将 SIP 规约为团问题
Suppose we want to check whether $G_2$ contains a clique of size $k$. We can construct a complete graph $G_1$ that has $k$ vertices, and check whether $G_1$ is isomorphic to a subgraph of $G_2$. The construction takes $O(|V|^2)$ time since $k \leq |V|$ without the loss of generality.
$CLIQUE \Rightarrow SIP$:
The clique is a subgraph of $G_2$ and isomorphic to $G_1$.
$SIP \Rightarrow CLIQUE$:
A subgraph in $G_2$ has $k$ vertices and is complete.

### 34.5-7
**The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is NP-complete.**


为了证明一个问题是 NP 完全的，需要满足两个条件：
1） 问题的$L \in 𝑁$；
2） 对所有 $NP$ 中的 $L’$，有$L'\leq_pL$。
为了证明最长简单回路问题，我们首先用数学语言明确一下条件，然后把这个最优化问题转换为决策问题。

**Step 1.**
- 设该问题为 LSCP，输入为一个图 G 和一个正整数 k（表示决策问题的判定阈值），输出 是一个布尔值，表示是否存在超过阈值的长简单回路（0 或 1）。

那么对于这样一个问题，要成为 NP 完全，需要证明条件里的两点，首先证明第一点，即 $LSCP \in N$

**Step 2.**
- 要证明 LSCP 是一个 NP 问题，需要给任意实例 x 提供一个在多项式时间内可被验证的证书 y。
- 我们可以将图 G 中一个长度至少为 k，满足为简单回路的顶点序列作为证书。
- 那么给定输入 G 和 k 时，就可以在多项式时间内，通过检查该序列是否满足长度至少为 k 且为简单回路，来验证证书（时间约为$O(n^2)$），n 为 G 编码长度）。

接下来，就要证明 LSCP 为 NP-hard 了，需要证明对 NP 中任意问题，都不比 LSCP 更简单。

**Step 3.**
- 我们可以通过将 LSCP 归约为一个已知的 NP-hard 问题来证明该点。在这里可以用一个非常契合的问题，即哈密顿回路问题。
- 哈密顿回路问题可以表示为 $HAM-CYCLE = \{<G>: G \text{是哈密顿图}\}$。哈密顿图的定义是图中包含哈密顿回路，而哈密顿回路是指一个访问图中每个定点有且仅有一次的一个简单回路。
- 为了将 HAM-CYCLE 归约为 LSCP，我们可以将 k 设为图中顶点的总数 sum，则对任意HAM-CYCLE 的实例，都能转换为 k=sum 的 LSCP 问题，该 LSCP 决策问题就变为了判定图中是否存在长度不小于定点总数的简单回路，即哈密顿回路，那么该决策问题就与哈密顿回路问题完全等价了，所以任何 HAM-CYCLE 中的实例都能在多项式时间内转换为一个相同解的 LSCP 问题，即$L_{\text{HAM-CYCLE}}\leq_pL_{\text{LSCP}}LSCP$，因为 HAM-CYCLE 为一个 NP-hard 问题，而 LSCP 难度不小于 HAM-CYCLE，因此 LSCP 也是一个 NP-hard 问题。

**Step4.**
综上两点所述，LSCP 满足作为 NP 完全问题的所有条件，因此，LSCP 为一个 NP 完全问题。