# np

## 1 P & NP & NPC

• class P: consists of problems that are solvable is polynomial time.
• class NP: consists of problems that are verifiable in polynomial time.
• varifiable: given a certificate of a solution,

we could verify that the certificate is correct in time polynomial in the size of the input to the problem.

$$P \subseteq NP$$

• NPC: NP-complete. it is in NP and is as hard as any problem in NP.

If any NP-complete problem can be solved in polynomial time, every problemm in NP has a polynomial algorithm.

• co-NP: the set of languages L such that $$\overline{L} \in NP$$

### 1.1 3 key concepts in showing a problem to be NP-complete

#### 1.1.1 Decision problem and optimization problem

Optimization problem: each feasible solution has an associated value, we wish to find one with the best value.

Decision problem: Answer is yes or no

Optimization problem 可以加一个 threshold 让它变成 decision problem. 因此，只要OP是简单的，DP也是简单的。

#### 1.1.2 Reductions

• the transformation takes polynomial time
• the answers are the same.

That is, the answer for $$\alpha$$ is yes if and only if answer for $$\beta$$ is yes

the procedure is called a polynomial-time reduction algorithm.

1. given an instance $$\alpha$$ of A, use procedure to transform it into $$\beta$$ of B.
2. run P on B
3. use answer of $$\beta$$ for $$\alpha$$.

## 2 Intro problems

• an instance of a problem: the input to a problem. E.g. Graph G for PATH problem.

### 2.1 Shortest simple path

complexity: 即使包含负边，也可以在$O(VE)$找到。

### 2.2 Longest simple path

complexity: 都是NP-Complete。

### 2.3 Euler tour

complexity: 决定一个图是否含有Euler tour，$$O(E)$$.

### 2.4 hamiltonian cycle

complexity: 决定一个有向图是否含有hamiltonian cycle是NP-Complete

### 2.5 2-CNF/3-CNF satisfiability

• k-CNF: k-Conjuntive normal form
• A boolean formula is satisfiable if 它包括的变量去一种0和1的组合，可以使其值为1.
• A boolean formula is in k-CNF if it is AND of clauses of ORs of exactly k variables or their negations.

$$(x_1 \vee \neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (\neg x_2 \vee \neg x_3)$$ is 2-CNF.

complexity: determine whether 2-CNF is satisfiable is P, determine whether 3-CNF is satisfiable is NP-complete

## 3 NPC and reducitility

### 3.1 reducitility

• language $$L_1$$ is polynomial-time reducible to $$L_2$$, written $$L_1 \le_p L_2$$,

if 存在P时间的函数f, s.t. $$x \in L_1$$ if and only if $$f(x) \in L_2$$

Lemma 34.3: if $$L_1 \le_p L_2$$, then $$L_2 \in P$$ implies $$L_1 \in P$$.

### 3.2 NPC & NPH

a language $$L \subseteq {0,1}^*$$ is NP-complete if:

1. $$L \in NP$$
2. $$L' \le_p L$$ for every $$L' \in NP$$

NP-hard: L satisfies 2 but not 1.

Theorem 34.4: 如果任意一个NPC problem都是P solvable的，那么$$P=NP$$. 如果任意NP problem都不是P solvable的，那么所有NPC problem都不是P solvable的。

## 5 Homeworks

### 5.1 34.1-6

If $$L_1,L_2 \in P$$, then

• $$L_1 \bigcup L_2 \in P$$
• $$L_1 \bigcap L_2 \in P$$
• $$L_1 L_2 \in P$$
• $$\overline{L_1} \in P$$
• $$L_1^* \in P$$

#### 5.1.1 Solution

Assume $$L,L_1,L_2 \in P$$:

• $$L_1 \bigcup L_2$$: decide if $$x \in L_1$$ and $$x \in L_2$$. 只要有一个成立，就会有$$x \in L_1 \bigcup L_2$$. Otherwise not.
• $$L_1 \bigcap L_2$$: 同上，只要两个都成立，就有$$x \in L_1 \bigcap L_2$$. Otherwise not.
• $$L_1L_2$$: $L1,L2$是两个字符串，$L1L2$是把两个连接起来。用$xij$来表示一个字符串的子串。

• $$\overline{L}$$: $$x \in \overline{L}$$ 等价于 $$x \notin L$$
• $$L^*$$:

Kleene star: $$L^*=\bigcup_{i\in N}L^k$$ where $$L^(k+1) = LL^k$$.

### 5.2 34.2-9

Prove that $$P \subseteq co-NP$$

#### 5.2.1 Solution

$$L \in P$$ => $$\overline{L} \in P \subseteq NP$$

### 5.3 34-1

#### 5.3.1 Solution

a).

INDEPENDENT-SET = { $< G,k >$:G is a graph containing a independent-set of size k }

Prove NPC:

b).

1. find the maximum size independent set. Since $$K \le |V|$$, $$O(V)$$.
2. Once the maximum K is found, we need to 决定哪些v在里面。

c).

d).

maximum independent set is the side with the larger number of vertices. 直接比较一下多少就可以，所以$$O(V)$$.