# 資訊工程理論

## Turning Machine
- $M = (K, Σ, δ, s)$
- $δ:K\times Σ\rightarrow(K\cup\{h,yes,no\})\timesΣ\times\{\leftarrow,\rightarrow,-\}$
- $M$ 在 $x$ 執行結果的四種可能性：
- yes $\rightarrow$ M accept x
- no $\rightarrow$ M reject x
- h $\rightarrow$ M(x) = y
- loop forever
- [**Theorem 1**](https://www.eecs.yorku.ca/course_archive/2008-09/W/6115/palindrome.pdf)：Palindrome 用 single-tape TM 解最差要 $Ω(n^2)$ steps。
- 考慮 $L=\{wc^{2n}w^R|w\in\{a,b\}^n\}$
- 這 $2^n$ 個 string 的 $n\sim3n$ 位置的 working sequence中
- 1.不同 string 的 working sequence 必定不一樣
- 2.同一 string 中必有長度 $\le\frac{T(4n)}{2n}$ 的
- 所有長度 $\le\frac{T(4n)}{2n}$ 的 working sequence 總數要超過 $2^n$
- $|Q|^{l+1}\ge 2^n$
- Church Turing Thesis
- 有許多計算的模型，但彼此都是等價的。
- 目前可以計算的問題，都可以用 TM 計算。
- Decidability and Recursive Languages
- decidable or recursive
- $x\in L \rightarrow M(x)=\text{"yes"}$
- $x\notin L \rightarrow M(x)=\text{"no"}$
- recursively enumerable / semidecidable
- $x\in L \rightarrow M(x)=\text{"yes"}$
- $x\notin L \rightarrow M(x)=\nearrow$
- **Proposition 2**：一個 recursive language $L$ 必定同時 recursive enumerable
- **Theorem 3**：每個 $f(n)$ time 的 k-string TM，都有等價的 $O(f^2(n))$ time 的 1-string TM。
- $M$ 需要 $f(n)$ 步，每一步
- 花 $kf(n)$ 時間知道所有資訊
- 花 $k^2f(n)$ 轉移
- 總時間為 $k^2f^2(n)=O(f^2(n))$
- **Theorem 4**：每個 $f(n)$ time 的 k-string TM，都有等價的 $O(f(n)logf(n))$ time 的 2-string TM。
- Refer to JACM [Two-Tape Simulation of Multitape Turing Machines](https://dl.acm.org/citation.cfm?id=321362)
- **Theorem 5**：如果 $L\in TIME(f(n))$，則 $L\in TIME(\epsilon f(n)+n+2)$
- 令 $m=\lceil\frac{6}{\epsilon}\rceil$，**state** 長相為 $K\times\{1,...,m\}^k\times\sum^{3mk}$
- 先花 n+2 時間，把 input 每 m 個 symbol 縮成一個 symbol。
- 接著每 m 步可以用 6 步模擬。
- 花 4 步蒐集前後資訊
- 花 2 步進行轉移
- **Theorem**：如果 $L\in SPACE(f(n))$，則 $L\in SPACE(\epsilon f(n)+2)$
- **Proposition**： $Palindrome$ 問題，使用兩個 counter 可以在 $O(logn)$ 空間判定。
- **Theorem 6**： 每個 $f(n)$ time 的 NTM，都有個等價的 $O(c^{f(n)})$ time 的 3-string DTM
- $c$ 是 $NTM$ 的最大 branch 數
- **Corollary 7**： $NTIME(f(n))\subseteq\cup_{c\ge1}TIME(c^{f(n)})$
- **REACHABILITY**： 圖中是否存在 a 到 b 的 path?
- $DTIME(n)$：BFS
- $NSPACE(logn)$：
- $x = a$, Guess $m$
- For $i = 1$ to $m$
- 1.Guess $y~\in$ V(G)
- 2.Check whether $(x,y)~\in$ E(G)
- 3.Check whether $y = b$
- 4.$x = y$
- Return no
## Undecidability
- $H=\{(M,x)|\text{ M halts on x}\}$ 是 recursive enumrable，但不是 recursive.
- 假設 $M_H$ decides $H$，藉由 $M_H$ 來建構 $D(M)$
- 如果 $M$ halts on $M$, $D(M)=\nearrow$
- 如果 $M(M)=\nearrow$, $D$ halts on $M$
- $\rightarrow D(D)$ is always contradiction
- Reduction
- **Theorem 8**：如果 $K$ reduce to $L$ 而且 $K$ undecidable，則 $L$ undecidable
- 假設我們要證 $L$ 是 undecidable
- 找到 undecidable language $K$
- 找到 computable function $f$
- 使得 $x\in K\iff f(x)\in L$
- Language Class：每一個 member 都是 language
- **RE**：Set of recursice enumerable languages.
- **coRE**：Set of languages whose complement is in **RE**.
- **R**：Set of recursive languages.
- 
- $RE$ 相關的性質：
- **Lemma 9**：$L\in R\rightarrow \bar{L}\in R$
- 因為可以 reverse $TM$ 的答案
- **Lemma 10 ( Kleene’s theorem )**：$L\in R\iff L\in RE,~\bar{L}\in RE$
- 因為可以平行的計算兩台 $TM$
- $R=RE\cap coRE$
- **Corollary 11**：$L\in RE,~L\notin R~~\rightarrow~~\bar{L}\notin RE$
- **Corollary 12**：$\bar{H}=\{M:x|M(x)=\nearrow\}\notin RE$
- $H$ 是 $RE-complete$
- 對 $L\in RE$，是否 $x\in L$ 的答案可以透過執行 $M_H(M_L,x)$
- 如果 $M_L$ halts on $x$：Run $M_L(x)$ and return
- 如果 $M_L$ loops on $x$：reject
- **Rice Theorem**
- **Property of Languages**：
- 基本架構：
- $RE=\{L_1,L_2,L_3,...\}=\{L(M_1),L(M_2),L(M_3),...\}$
- $Property=\{L|L\in RE~而且~L~有某些性質\}$
- **Nontrivial**
- $C\ne RE$
- $C\ne\phi$
- 定義是 recursively enumerable languages 的集合，但有時也是 TMs 的集合，因為可以一一對應。
- **Theorem 13：如果 $C\ne\phi$ 是 $RE$ 的 proper subset，則問題 "$L(M)\in C$" 是 undecidable.**
- 前提(不失一般性的假設)：
- $\phi\notin C$
- $L(M_L)\in C$
- $H=\{(M,x)|\text{ M halts on x}\}$ 歸約到 $C=\{M|L(M)\in C\}$
- 給定任意的 $M,x$，建構 $N(y)=$ Run $M$ on $x$
- $M$ halts on x：Run $M_L(y)$ and return.$~\rightarrow$ 表現得跟 $L(M_L)$ 一樣
- $M$ loops on x $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\rightarrow$ 表現得跟 $\phi$ 一樣
- **底下問題都是 undecidable：**
- 問一個 turing machine $M$ ， 是否 $L(M)\in C~?$
- 問一個 recursive enumerable language $L\in RE$ ， 是否 $L\in C~?$
- **Corollary 14**：
- $L(M)=\phi$
- $L(M)\text{ is finite}$
- $L(M)\text{ always halt}$
- $L(M)=\sum^*$
- $L(M)\text{ is regular}$
- $L(M)\text{ is context free}$
- 數學與邏輯上的 undecidable 例子：
- First-order logic
- Natural numbers with addition and multiplication
- Rational numbers with addition and multiplication
- 邏輯：
- 布林邏輯：只有用來代表真假值的簡單變數
- 謂詞邏輯：也有函數的概念
- 一階邏輯：加上 $\forall$ (對於所有) 或 $\exists$ (存在)
- [哥德爾不完備定理](https://programmermagazine.github.io/201403/htm/focus4.html#%E5%BE%9E%E7%A8%8B%E5%BC%8F%E4%BA%BA%E7%9A%84%E8%A7%92%E5%BA%A6%E8%AD%89%E6%98%8E%E5%93%A5%E5%BE%B7%E7%88%BE%E4%B8%8D%E5%AE%8C%E5%82%99%E5%AE%9A%E7%90%86)：
- 定理 G1：若公理化邏輯系統 T 是個包含基本算術 (皮諾公設)的一致性系統，那麼 T 中存在一種語句 S，但是你無法用 T 證明 S ，卻也無法否證 S。
- 定理 G2：若公理化邏輯系統 T 是個包含基本算術 (皮諾公設)的一致性系統，那麼 T 無法證明自己的一致性。
- 定理 G3：不存在一個程式，可以正確判斷一個「包含算術的一階邏輯字串」是否為定理。
## Boolean Logic
- Conjunctive Normal Forms
- Clause：Disjunction of literals
- $\phi=\wedge_{i=1}^nC_i$ 是 Conjuction of Clauses.
- Disjuctive Normal Form
- Implicants：Conjunction of literals.
- $\phi=\vee_{i=1}^nC_i$ 是 Disjuction of Implicants.
- 性質：
- **Any Expression φ Can Be Converted into CNFs and DNFs**
- Functional Completeness
- $\{\vee,\wedge,\neg\}$, $\{\text{NAND}\}$, $\{\text{NOR}\}$
- Boolean Expression 所形成的集合
- **SAT**：存在一個填法
- **UNSAT**：不存在任何填法
- **VALID**(tautology)：任何填法都對
- contingency：存在填法但不是任何填法都對。
- Boolean Functions
- 和 truth table 一一對應，共有 $2^{(2^n)}$ 種
- 和 boolean expression 一一對應
- **Corollary 15**：每個 function 有對應 $O(n2^n)$ 大小的 expression。
- Boolean Circuits
- 用一張圖來表示電路圖，$\{t,f,\land,\lor,\neg,x_1,...\}$
- 和 boolean expression 一一對應
- **Theorem 16**：存在 function ，使得對應 $\frac{2^n}{2n}$ 的 circuit 無法對應。
- 如果 $m=\frac{2^n}{2n}$，則 $((n+5)m^2)^m\le2^{2^n}$
## Complexity Classes
- 一些前提與假設：
- 一般指**時間或是空間**複雜度
- Proper Function
- 非嚴格遞增
- 存在 $M$ 使得對所有 $x$，$M(x)=1^{f(x)}$
- $M$ 用 $O(x+f(x))$ 時間
- $M$ 用 $O(f(x))$ 額外空間
- Precise Turing Machine
- $M$ 結束時恰好用 $f(x)$ 時間
- $M$ 結束時恰好用 $g(x)$ 額外空間
- **Proposition 17**：每一個 $f(n)$ time(space) 的 $TM$ 有個等價的 $O(f(n))$ time(space) 的 Precise $TM$。
- 我們所關心的最重要的 Complexity Classes：
- 時間：$P,~NP,~E,~EXP,~NEXP$
- 空間：$PSPACE,~NPSPACE,~L,~NL$
- 對於 deterministic 時間及空間的 $RE$ language，他們都 close under complement
- $P=coP$
- $PSPACE=coPSPACE$
- $L=coL$
- 定理與性質：
- $H_f=\{M:x~|~\text{M accepts x after at most f(|x|) steps.}\}$
- $H_f\in TIME(f(n)^3)$
- 構造一個 4-tape 的 universal $TM$，用 $O(f(n)^3)$ 時間來模擬任何一個 k-tape $f(n)$ 時間 $TM$，還要使用 alarm 來檢查時間
- $H_f\notin TIME(f(\lfloor\frac{n}{2}\rfloor))$
- 假設相反，可以在 $f(|M|)$ 時間決定 $M:M\in H_f~?$ 則建構 $D(M)$。
- $\text{M accepts M after at most f(|M|) steps}~\rightarrow~false$
- $\text{M doesn't accept M after at most f(|M|) steps}~\rightarrow~true$
- $D(D)$ 時間為 $f(|D|)$，$D(D)$ 總是會導致矛盾。
- [**The Time Hierarchy Theorem**](https://en.wikipedia.org/wiki/Time_hierarchy_theorem)
- **Theorem 18**：$TIME(f(n))\subsetneq TIME(f(2n+1)^3)$
- **Corollary 19**：$P\subsetneq E$
- $p\subseteq TIME(2^n)\subsetneq TIME((2^{2n+1})^3)\subseteq E$
- [**The Space Hierarchy Theorem**](https://en.wikipedia.org/wiki/Space_hierarchy_theorem)
- **Theorem 20**：$SPACE(f(n))\subsetneq SPACE(f(n)logf(n))$
- **Corollary 21**：$L\subsetneq PSPACE$
- **Nondeterministic Time Hierarchy Theorem**
- **Theorem 22**：$NTIME(n^r)\subsetneq NTIME(n^s)$ 對於 $r<s$
- **Theorem 23**：$NTIME(T_1(n))\subsetneq NTIME(T_2(n))$ 對於 $T_1(n+1)=o(T_2(n))$
- **Theorem 24**
- 1.$SPACE(f(n))\subseteq NSPACE(f(n))$
$~~~TIME(f(n))\subseteq TIME(f(n))$
- 2.$NTIME(f(n))\subseteq SPACE(f(n))$
- 3.$NSPACE(f(n))\subseteq TIME(k^{logn+f(n)})$
- 性質與推論：
- Configuration Graph 有 $c^{f(n)}$ nodes
- 假設 $NTM$ 的空間有 bound，則 configuration 數量有上限，可以用指數時間的 $DTM$ 來做 Reachability 問題。
- 當模擬時間太久時，必定會出現 loop。
- 重要關係式：$L\subseteq NL\subseteq P\subseteq NP\subseteq PSPACE\subseteq EXP$
- **(Savitch’s Theorem) Theorem 25**：$REACHABILITY\in log^2n$
- 
- 定義 $PATH(x,y,i)$ 為是否存在 $x$ 到 $y$ 長度小於等於 $2^i$
- 1.深度為 $logn$
- 2.每一層存 $(x,y,i)$，大小為 $logn$
- **Corollary 26**：$NSPACE(f(n))\subseteq SPACE(f(n)^2)$
- Configuration Graph 有 $c^{f(n)}$ nodes
- 1.深度為 $log(c^{f(n)})=f(n)$
- 2.每個 node 大小為 $f(n)$ 個 bits
- 因此可用 $f^2(n)$ 空間解決等價的 Reachability 問題。
- **Corollary 27**：$PSPACE=NPSPACE$
- **Immerman's Theorem**：
- $NL=coNL$
- $NSPACE=coNSPACE$
## Reduction
- $A$ reduces to $B$
- 透過解 $B$ 的方法，可以用來解 $A$。
- $B$ 至少跟 $A$ 一樣難，或是比 $A$ 更難。
- **Karp Reduction** $R$，$x\in A\iff R(x)\in B$
- 
- Reduction 的步驟，希望空間和時間夠小。
- $B$ 不一定是 **onto**。
- 例子：
- $hamiltonian~path~\rightarrow~sat$
- 有 $n^2$ 個變數 $x_{ij}$，代表 path 的第 $i$ 個城市是城市 $j$。
- 1.每個城市至少出現在某一位置。
- 2.每個城市不出現超過兩次。
- 3.每個位置至少有一城市。
- 4.每個位置不出現超過兩城市。
- 5.相鄰的位置的城市，都是原圖上有出現的邊。
- 根據以上觀察，可以建構出 $O(n^3)$ 個長度 $O(n)$ 兩層 $CNF$。
- $reachability~\rightarrow~circuit~value$
- $g_{ijk}$ 代表存在 $i$ 到 $j$ 只經過 $\{1,2,...,k\}$ 節點的路徑。
- $h_{ijk}$ 代表存在 $i$ 到 $j$ 經過 $k$ ，且只經過 $\{1,2,...,k\}$ 節點的路徑。
- $h_{ijk}=g_{i,k,k-1}\land g_{k,j,k-1}$
- $g_{ijk}=g_{i,j,k-1}\lor h_{i,j,k}$
- 設定 $g_{ijk}=true\iff i=j~or~(i,j)\in E$，結果為 $g_{1nn}$
- $circuit~sat~\rightarrow~SAT$
- 
- 這是一個 polynomial time reduction，如果用 $((x_1\land x_2)\land(x_3\lor x_4))\lor\neg(x_3\lor x_4)$ 則時間複雜度會變 exponential 在最糟情況下。
- 每一個 gate 都有對應的 $SAT$ 變數，$SAT$ 變數數量為 circuit 數量加上 circuit 變數數量。
- **Proposition 28**：如果 $R_{12}$ 是 $L_1$ 到 $L_2$ 的 Reduction，且 $R_{23}$ 是 $L_2$ 到 $L_3$ 的 Reduction，則 $R_{13}$ 是 $L_1$ 到 $L_3$ 的 Reduction。
- 我們不可以先執行 $R_{12}(x)$，他可能會需要 polynomial 的空間，但我們要求可以在 $O(logn)$ 空間完成。
- 模擬 $R_{23}$ 的 $TM$ 所做的操作，每次當他需要一個 bit，**重頭開始**模擬 $R_{12}$ 的 $TM$ 直到產生對應的 bit。
- **Completeness：**
- 問題可以用 Reduction 比較難度。
- 每個複雜度 $C$ 中，我們都可以找到最難的問題。
- $L~是~C-complete$
- $L\in C$
- $L~是~C-hard$：所有 $L'\in C$ 可以 $O(logn)$ reduces 到 $L$。
- **Closedness under Reduction**
- 每個複雜度 $C$ 是 closed under reduction $\iff$ $A$ 可以 reduce 到 $B\in C$，則 $A\in C$
- 常見的複雜度中：
- $P, NP, coNP, L, NL, PSPACE, EXP$ 都是 closed under reduction。
- $E$ 不是 closed under reduction。
- **Proposition 29**：如果 $L$ 是 $C$-complete 而且 $C'\subseteq C$，則 $C=C'\iff L\in C'$
- **Corollary 30**：$P=NP\iff\text{某個 NP-complete 問題在 P 中}$
- **Corollary 31**：$L=P\iff\text{某個 P-complete 問題在 L 中}$
- **Proposition 32**：如果 $L$ 是 $C$-complete 且 $L$ 是 $C'$-complete 則 $C=C'$
- **Proposition 33**：如果 $L$ 是 $C$-complete 且 $L$ 可以規約到 $L'\in C$ 則 $L'$ 是 $C$-complete。
- **Table of Computation：**
- 
- 假設時間是 $n^k$，則表格大小： $n^k行\times n^k列$
- 每一個 $DTM$ 在 $x$ 上的運算可以用 **一個 table** 表示 → 建構對應 boolean function
- **Theorem 34 (Ladner, 1975)**：$circuit~value$ 是 $P$-complete。
- $circuit~value\in P$
- 每一個 $L\in P$，背後對應的 table，可以設計一個 $circuit~value$ 去解決。
- **Corollary 35**：如果 $L\in TIME(T(n))$，則存在 $O(T(n)^2)$ 的電路(沒變數) decides $L$。
- 每一個 $NTM$ 在 $x$ 上的運算可以用 **多個 table** 表示 → 建構對應 boolean expression
- **Theorem 39 (Cook, 1971)** ： $SAT$ 是 $NP$-complete.
- $SAT\in NP$
- $circuit~sat → SAT$
- 每一個 $L\in NP$，背後對應的**那些** table，可以設計一個 $circuit~sat$ 去解決。
- **Corollary 40** ： 如果 $L\in NTIME(T(n))$，則存在 $O(T^2(n))$ 的電路(有變數) decides $L$。

## P/NP-Complete Problems
- **P-Complete Problems**
- **Monotone Circuit**：
- 當只有一個 input 改變時，電路的結果不會變
- 不存在 not gate
- **Corollary 36 (Goldschlager, 1977)**：$monotone~circuit~value$ 是 $P$-complete。
- 藉由 De Morgan’s Law 歸約 $circuit~value$ 到 $monotone~circuit~value$
- **Theorem 37 (Goldschlager, 1977)**：$planar~monotone~circuit~value$ 是 $P$-complete。
- **Theorem 38 (Goldschlager, Shaw, & Staples, 1982)**：$maximum~flow$ 是 $P$-complete。
- **NP 等價定義：**
- **Proposition 41 (Edmonds, 1965)** ： $L\in NP$ $\iff$ $L=\{~x~|~\exists y~(x,y)\in R\}.$
- 其中 $R$ 是 polynomial decidable 且 polynomial balanced
- polynomial decidable：$\{$<$x,y$>$|(x,y)\in R\}\in P$
- polynomial balanced：$(x,y)\in R\rightarrow |y|\le|x|^k$
- 證明：
- 往右：$R$ 就是檢查 $NTM$ 在 $x$ 上根據 path $y$ 的步驟執行是否 accept。
- 往左：猜測任何一個 path $y$，並檢查是否 $(x,y)\in R$
- **NP-Complete 問題：**
- [Karp's 21 NP complete Problem](https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf)
- $\text{3SAT}$：
- 問題：給定一個 $3CNF$ ，問是否 satisfiable
- 方法一：$circuit~sat\rightarrow 3SAT$
- Reduction 本身每一個 clause 就最多 3 個 literals
- 可以透過 duplicate 讓每個 calause 恰好 3 個 literals。
- 方法二：$SAT\rightarrow 3SAT$
- $a\lor b\lor c\lor d\lor e\rightarrow (a\lor b\lor t_1)\land(\overline{t_1}\lor c\lor t_2)\land(\overline{t_2}\lor d\lor e)$
- $\text{3SAT}'$：
- 問題：給定一個 $3CNF$ 其中 variables 最多三次，literals 最多兩次，問是否 satisfiable
- 方法：$3SAT\rightarrow 3SAT'$
- $3SAT：(x\lor a\lor b)\land(x\lor c\lor d)\land(\neg x\lor e\lor f)$
- $3SAT'：(x_1\lor a\lor b)\land(x_2\lor c\lor d)\land(\neg x_3\lor e\lor f)\land(x_1\Rightarrow x_2\Rightarrow x_3\Rightarrow x_1)$
> **Proposition 42**：$\text{3SAT}'$ 是 NP-complete

> [$2SAT\in P$](https://blog.csdn.net/JarjingX/article/details/8521690)
- $\text{MAX2SAT}$：
- 問題：給定一個 $2CNF$ ，問是否能夠 satisfy k 個 clauses
- 方法：$3SAT\rightarrow MAX2SAT$
- $(a\lor b\lor c)\rightarrow$
- $a\land b\land c\land w$
- $(\neg a\lor\neg b)\land(\neg b\lor\neg c)\land(\neg c\lor\neg a)$
- $(a\lor\neg w)\land(b\lor\neg w)\land(c\lor\neg w)$
- 如果 $(a\lor b\lor c)$ 是 True ，則可以設定 $w$ 使得恰有 7 個 clause 是 True
- $\phi$ 有 m 個 clause $\Rightarrow$ $R(\phi)$ 有 10m 個 clause
- $\phi$ 是 True $\iff$ 至少 7m 個 clause 是 True
- $\text{NAESAT}$：
- 問題：給定一個 $3CNF$ ，問是否 NAE-satisfiable
- 方法：$3SAT\rightarrow NAESAT$
- $a\lor b\lor c\rightarrow (a\lor b\lor x)\land(c\lor \bar{x}\lor F)$
- $\phi$ 是 satisfiable $\iff$ $R(\phi)$ 是 NAE-satisfiable
- $F$ 是獨立於每一個 clause 的一個變數
- 往右：
- $F=0$
- $c=0~或~a=b=c=1：x=0$
- $其他：x=1$
- 往左：不失一般性從 $T$ 或 $\bar{T}$ 挑選 $F=false$ 出發：
- 因為 $T$ 是 NAE-satisfiable $\iff$ $\bar{T}$ 是 NAE-satisfiable
- $x=1\rightarrow c=1$
- $x=0\rightarrow a=1\lor b=1$
- $\text{Independent Set}$：
- 問題：給定一個圖 $G$，問是否存在 $k$ 個點的集合，彼此間沒有任何邊相連
- 方法：$3SAT\rightarrow Independent~Set$
- 每一個 clause 建立三角形
- 每一個 $x$ 和 $\neg x$ 建立一個邊
- 
- k 個 clause 的 $3CNF$ 是 satisfialbe $\iff$ 圖中有大小為 k 的 independent set
> **Corollary 43**：4-degree graphs
> **Theorem 44**：planar graphs
> **Theorem 45 (Garey & Johnson, 1977))**：3-degree planar graphs
> **Corollary 46**：$Vertex~Cover$ 是 NP-complete
> **Corollary 47**：$Clique$ 是 NP-complete
- $Vertex~Cover$
- 問題：給定一個圖 $G$，問是否存在 $k$ 個點的集合，可以覆蓋所有的邊
- 方法：$Independent~Set\rightarrow Vertex~Cover$
- $I$ 是 $Independent~Set$ $\iff$ $V-I$ 是 $Vertex~Cover$
- $Clique$
- 問題：給定一個圖 $G$，問是否存在 $k$ 個點的集合，彼此間兩兩有邊相連
- 方法：$Independent~Set\rightarrow Clique$
- $I$ 是 $G$ 的 $Independent~Set$ $\iff$ $I$ 是 $\bar{G}$ 的 $Clique$
- **一些圖論覆蓋問題：**
- 點集合支配所有點：dominating set
- 點集合覆蓋所有邊：vertex cover
- 邊集合支配所有點：paired dominating set
- 邊集合覆蓋所有點：maximum matching
- $\text{MIN CUT , MAX CUT}$
- $\text{MIN CUT}\in P$：maximum flow 演算法
- 問題：給定一個圖 $G$，把圖拆分成兩個非空部分，使得兩部分之間相連的邊數最少
- $\text{MAX CUT}$ 是 NP-complete
- 問題：給定一個圖 $G$，把圖拆分成兩個非空部分，使得兩部分之間相連的邊數至少 $k$
- 方法：$NAESAT\rightarrow\text{MAX CUT}$
- $3CNF$ 有 $m$ 個 clauses 及 $n$ 個 variables
- $G$ 有 $2n$ 個點，$x_1,\neg x_1,...,x_n,\neg x_n$
- 對於有三個不同 literals 的 clause，把對應三點建立一個三角形
- 對於只有兩個不同 literals 的 clause，把對應兩點建立兩個邊
- 根據 $x_i$ 和 $\neg x_i$ 總共出現 $n_i$ 次，把 $G$ 中的 $x_i$ 和 $\neg x_i$ 建立 $n_i$ 個邊
- $\sum n_i=3m$
- 
- 證明： $m$ 個 clause 的 $3CNF$ 是 NAE satisfialbe $\iff$ 圖中有大小至少為 $5m$ 的 cut
- 往左：圖上有大小至少為 $5m$ 的 cut
- 每一個 clause，對 cut 的貢獻最多是 $2$
- 如果 $x_i$ 和 $\neg x_i$ 在同一側，他們貢獻的 cut 最多只有 $2n_i$ 個邊
- 一定有一個點只貢獻最多 $n_i$ 個邊
- 我們可以把那個點換到另外一側，過程中 cut 的數量不會變少
- 不失一般性，每個 $x_i$ 和 $\neg x_i$ 在不同側，
- $x_i$ 和 $\neg x_i$ 的貢獻總共是 $3m$
- cut 中至少有 $2m$ 是來自每一個 clause
- 因此每一個 clause 的貢獻都是 $2$
- 因此每一個 clause 都是 NAE satisfialbe
- 往右：$3CNF$ 是 NAE satisfialbe
- 把所有 true 的 literal 放到一側，false 的 literal 放到另一側，這個 cut 的大小就至少 $5m$
- 這裡證明了 multi graph 的 $\text{MAX CUT}$ 是 NP-complete，其實一般圖上的 $\text{MAX CUT}$ 也是 NP-complete
- $\text{MAX BISECTION}$
- 問題：給定一個圖 $G$ 及目標 $k$，問是否存在**至少** $k$ 個邊的集合，可以用這些邊把圖拆分成**兩個大小相同的點集合**
- 方法：$\text{MAX CUT}\rightarrow\text{MAX BISECTION}$
- $G$ 有 $n$ 個點 $m$ 個邊，問是否有大小至少 $k$ 個邊的集合
- $G'$ 有 $2n$ 個點 $m$ 個邊，構造方法為把 $G$ 在額外多增加 $n$ 個點即可，並且目標 $k'=k$
- $G$ 有大小至少 $k$ 的 CUT $\iff$ $G'$ 有大小至少 $k$ 的 bisection
- $\text{BISECTION WIDTH}$
- 問題：給定一個圖 $G$，問是否存在**最多** $k$ 個邊的集合，可以用這些邊把圖拆分成**兩個大小相同的點集合**
- 方法：$\text{MAX BISECTION}\rightarrow\text{BISECTION WIDTH}$
- $G$ 有 $2n$ 個點 $m$ 個邊，問是否有大小至少 $k$ 個邊的集合
- $G'=\bar{G}$，問是否有大小至少 $n^2-k$ 個邊的集合
- $G$ 有大小至少 $k$ 的 bisection $\iff$ $G'$ 有大小最多 $n^2-k$ 的 bisection
- $G$ 有大小 $k$ 的 bisection $\iff$ $G'$ 有大小 $n^2-k$ 的 bisection
- $\text{Hamiltonian Path}$
- 問題：給定一個圖 $G$，問是否存在 Hamiltonian Path
- 不特別指定起點跟終點
- 方法：$3SAT\rightarrow\text{Hamiltonian Path}$ [Ref](https://www.geeksforgeeks.org/proof-hamiltonian-path-np-complete/)
- 
- 
- $3CNF$ 有 $m$ 個 clauses 及 $n$ 個 variables
- $G$ 中有 $n$ 個 diamonds 加上 $m$ 個 nodes
- 每個 diamond 中間有 $m$ 個 pair，另外再用 $m-1$ 個獨立點隔開
- 因此圖上有 $n+1+n(3m+1)+m$ 個點
- 每個 clause 的三個 literals 建立三對邊
- positive：從左往右
- negative：從又往左
- $3CNF$ 是 satisfiable $\iff$ $G$ 有 Hamiltonian Path
> **Theorem 48**：$\text{Hamiltonian Path}$ 是 NP-complete
> **Corollary 49**：$\text{TSP}$ 是 NP-complete
> **Corollary**：$\text{Hamiltonian Cycle}$ 是 NP-complete
- $\text{TSP}$ (decision version)
- 問題：給定一個有權重的圖 $G$ 及目標 $k$ ，問是否存在距離總和最多 $k$ 的 $\text{Hamiltonian Cycle}$
- 方法：$\text{Hamiltonian Path}\rightarrow\text{TSP}$
- $G$ 有 $n$ 個點 $m$ 個邊，問是否有 $\text{Hamiltonian Path}$
- $G'$ 是 $n$ 個點的 complete graph，目標為 $k=n+1$
- 原圖有邊：weight = 1
- 原圖無邊：weight = 2
- $G$ 有 $\text{Hamiltonian Path}$ $\iff$ $G'$ 有距離最多 $k=n+1$ 的 $\text{Hamiltonian Cycle}$
- $\text{3-coloring}$
- 問題：給定一個圖 $G$ ，問是否可用三種顏色使相鄰兩點不同色
- 方法：$\text{NAESAT}\rightarrow\text{3-coloring}$
- 
- $3CNF$ 有 $m$ 個 clauses 及 $n$ 個 variables
- $G$ 中有 $n$ 個 a-三角形，加上 $m$ 個三角形
- $G$ 的點數為 $1+2n+3m$
- $G$ 的邊數為 $3n+6m$
- $3CNF$ 是 NAE-satisfiable $\iff$ $G$ 是 3-colorable
- **chromatic number $\chi(G)$**：圖 $G$ 至少要幾個顏色才可以使相鄰不同色
- $2coloring\in P$
- $\text{3 Dimensional Matching}(3DM)$
- 問題：給定 $3$ 個大小為 $n$ 的集合 $A,B,C$，以及三元關係 $T\subseteq A\times B\times C$，問是否可以從 $T$ 中取 $n$ 個 triple，彼此沒有共同的元素
- 方法：$3SAT\rightarrow 3DM$ [ref](https://math.stackexchange.com/questions/1312480/reduction-from-3sat-to-3-dimensional-matching)
- 
- 相關問題：
- 給定目標 $U$ 及一些它的子集合 $S_1,S_2,...,S_n$
- $\text{Set covering}$：是否能取恰好 $k$ 個 subset 使得聯集為 $U$
- $\text{Set packing}$：是否能取恰好 $k$ 個 subset 使得彼此沒有共同元素
- $\text{x3c}$：每個 subset size 都是 $3$ 且 $|U|=3m$，是否能取恰好 $m$ 個 subset 使得聯集為 $U$
> **Theorem 50(Karp, 1972)**：$3DM$ 是 NP-complete
> **Corollary 51(Karp, 1972)**：Set Covering, Set Packing, x3c 都是 NPC
> [X演算法](https://zh.wikipedia.org/wiki/X%E7%AE%97%E6%B3%95)
> [Dancing Links](https://zh.wikipedia.org/wiki/%E8%88%9E%E8%B9%88%E9%93%BE)
- $\text{SUBSET SUM}$
- 問題：給定 $n$ 個數字及目標 $k$，是否存在某些數字使得總和為 $k$
- 方法：$x3c\rightarrow \text{SUBSET SUM}$
- $x3c$ 給定 $n$ 個大小為 $3$ 的 subset，及目標 $U=\{1,...,3m\}$
- 有 $n$ 個數字，每個數字為對應長度 $3m$ 的 bit string 用 $n+1$ 進位來看，並且目標為對應長度 $3m$ 的 $11...11$ 用 $n+1$ 進位來看
- 例如 $n=3，m=2，U=\{1,2,3,4,5,6\}$
- $S_1=\{4,5,6\}$
- $S_2=\{1,5,6\}$
- $S_3=\{1,2,3\}$
- 目標變成 $111111_4=1365$
- $n_1=000111_4=21$
- $n_2=100011_4=1029$
- $n_3=111000_4=1344$
- $x3c$ 有解 $\iff$ $\text{SUBSET SUM}$ 有解
- $\text{Knapsack}$
- 問題：給定 $n$ 個物品有自己的重量以及價值，及目標 $W,K$，問是否有一種取法可以使得重量最多 $W$，價值至少 $K$。
- 方法：$\text{SUBSET SUM}\rightarrow\text{Knapsack}$
- $\text{SUBSET SUM}$ 給定 $n$ 個數字及目標 $T$
- 對應 $n$ 個物品重量及價值皆為原本的數字，目標的 $W,K$ 都設定成 $T$
- $\text{SUBSET SUM}$ 有解 $\iff$ $\text{Knapsack}$ 有解
- $\text{Bin packing}$
- 問題：給定 $n$ 個數字及目標 $B,C$，是否可以把這些數字分成 $B$ 群使得每一群數字總和最多 $C$
- 方法：$3DM\rightarrow3partition\rightarrow\text{Bin packing}$ [ref](https://cs.stackexchange.com/questions/72411/proof-that-bin-packing-is-strongly-np-complete)
- $\text{Integer Programming}(IP)$
- 問題：線性方程組是否有整數解
- 方法：$\text{SET COVERING}\rightarrow\text{Integer Programming}$
- $IP\in NPC$
- $LP\in P$
- **討論：**
- 限制問題的範圍 (problem instance)，通常問題可能比較簡單，但也可能不變
- $Knapsack$ 變成有數字範圍的 $Knapsack$
- $SAT$ 變成 $3SAT$
- $SAT$ 變成 $2SAT$
- 限制答案的範圍 (solution space)，問題可能變簡單、不變、或是變困難
- $LP$ 變成 $IP$
- $SAT$ 變成 $NAESAT$
- $3coloring$ 變成 $2coloring$
## coNP Problems
- **NP** 定義：
- 存在一台 nondeterminisitc TM $M$
- $x\in L$，則 $M(x)=$"yes" 對某些的 computation paths
- $x\notin L$，則 $M(x)=$"no" 對所有的 computation paths
- yes instance 有 short proof
- **coNP** 定義：
- $L\in coNP\iff \bar{L}\in NP$
- 存在一台 nondeterminisitc TM $M$
- $x\in L$，則 $M(x)=$"yes" 對所有的 computation paths
- $x\notin L$，則 $M(x)=$"no" 對某些的 computation paths
- no instance 有 short proof
- 三個證明 $L\in coNP$ 的方法：
- 1.證明 $\bar{L}\in NP$
- 2.證明 no instance 有 short proof
- 3.找一個對應的演算法
- **coNP 問題**：
- $\text{SAT complement}$
- 定義：所有的 $T$ 都是 false。
- $\phi\notin\text{SAT complement}\iff\phi有某個~T~是\text{true}$
- $\text{Hamiltonian Path complement}$
- 定義：不存在 $\text{Hamiltonian Path}$ 。
- $G\notin\text{Hamiltonian Path complement}\iff G有某個\text{Hamiltonian Path}$
- $\text{Validity}$
- 定義：所有的 $T$ 都是 true。
- $\phi\notin\text{Validity}\iff\phi有某個~T~是\text{false}$
- **coNP 等價定義：**
- **Proposition 54 (Edmonds, 1965)** ： $L\in coNP$ $\iff$ $L=\{~x~|~\forall y~(x,y)\in R\}.$
- 其中 $R$ 是 polynomial decidable 且 polynomial balanced
- polynomial decidable：$\{$<$x,y$>$|(x,y)\in R\}\in P$
- polynomial balanced：$(x,y)\in R\rightarrow |y|\le|x|^k$
- 證明：
- 直接基於 NP 等價定義
- $\bar{L}\in NP，\bar{L}=\{~x~|~\exists y~(x,y)\in \bar{R}\}$
- **Proposition 55** ： $L$ 是 $NP$-complete $\iff$ $\bar{L}$ 是 $coNP$-complete
- **P、NP、coNP可能關係**
- **P=NP=coNP**
- **P≠NP=coNP**
- **P≠NP≠coNP**
- **The Primality Problem**
- 檢測一個數字是否為質數。
- [$PRIMES\in P$](https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf)
- 
- $PRIMES\in coNP$
- 給定任何一個它的因數，即可證明它不是質數
- $PRIMES\in NP$
- **Theorem 56 (Lucas & Lehmer, 1927)**：$p$ 是質數 $\iff$ 存在 $1<r<p$ 使得：
- $r^{p-1}=1~mod~p$
- $r^{p-1/q}\ne1~mod~p$，其中 $q$ 為任意 $p-1$ 的直因數
- $C(23)$$=(5; 2, C(2), 11, C(11))\\= (5; 2, C(2), 11,(2; 2, C(2), 5,(2; 2, C(2))))$
- **Lemma 58**：$C(p)$ 的長度最多為 $5 log_2^2p$
- 給定 $C(p)=(r;a_1,a_2,...,a_n)$，即可證明 $p$ 是質數
- 我們可以檢查 $r^{p-1}~mod~p$ 是否為 1
- 我們可以檢查 $a_1,a_2,...,a_n$ 是否為 $p-1$ 所有的質因數
- 是否為質數、是否為因數、$p-1$ 是否沒有其他因數
- **Theorem 57 ([Pratt’s Theorem](https://www.cmi.ac.in/~ramprasad/lecturenotes/comp_numb_theory/lecture17.pdf))：$PRIMES\in NP\cap coNP$**
- 數論：
- $\Phi(n)=\{m|gcd(m,n)=1\}$
- $\Phi(13)=\{1,2,3,4,5,6,7,8,9,10,11,12\}$
- $\Phi(12)=\{1,5,7,11\}$
- $\phi(n)=|\Phi(n)|$
- 質數：$\phi(p)=p-1$
- $\phi(13)=12$
- 合數：**Lemma 59**：$\phi(n)=n\prod(1-\frac{1}{p_i})$
- $\phi(12)=12(1-\frac{1}{2})(1-\frac{1}{3})=4$
- **Corollary 60**：如果 $gcd(m,n)=1$ ， 則 $\phi(mn)=\phi(m)\phi(n)$
- $\phi(12)=\phi(4)\phi(3)=2\times2=4$
- **Lemma 61 (Gauss)**：$\sum\limits_{m|n}\phi(m)=n$
- $12=\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12)\\~~~~=1+1+2+2+2+4$
- The Chinese Remainder Theorem
- Fermat’s “Little” Theorem
- **Lemma 62(Fermat)**：如果 $p$ 是質數，則 $a^{p-1}=1~mod~p$
- $\Phi(p)=\{1,...,p-1\}$
- $a\Phi(p)=\{a,...,a(p-1)\}$
- **Corollary 63**：對任意數 $n$，$a^{\phi(n)}=1~mod~n$
- $\Phi(n)=\{~i~|~gcd(i,n)=1~\}$
- $a\Phi(n)=\{~ai~|~gcd(i,n)=1~\}$
- **Lemma 64**：單變數 $k$ 次多項式，在 module $p$ 時最多只有 $k$ 個根。
- 高斯：代數基本定理
- **Exponent of m**：最小的 $k$ 使得 $m^k=1~mod~p$
- $\{1,2,...,p-1\}$ 的每一個數字都有 exponent
- 每一個數字的 exponent 必定整除 $p-1$
- $R(k)$ 為 $\{1,2,...,p-1\}$ 之中 exponent 值為 $k$ 的個數
- $R(k)\ne 0\iff k|p-1$：基於 **Lemma 62**
- $R(k)\le k$：直接基於 **Lemma 64**
- $R(k)\le \phi(k)$：考慮：$x^k=1~mod~p$
- 假設存在 $s$ 的 exponent = $k$
- $1,s,s^2,...,s^{k-1}$就是方程式的 $k$ 個不同的根
- $s^l$ 的 exponent 是 $k$ $\iff$ $l\in\Phi(k)$
- 假設不存在 $s$ 的 exponent = k，$R(k)=0$
- $p-1=\sum\limits_kR(k)=\sum\limits_{k|p-1}R(k)\le\sum\limits_{k|p-1}\phi(k)=p-1$
- $k|p-1~時，~R(k)=\phi(k)$
- $\text{Otherwise}，~R(k)=0$

## Function Problem
- 比較：
- Decision Problem 是一個是非題。
- Function Problem 是一個最佳化問題。
- 廣義來說，"最佳化問題"**至少**比"是非題"難。
- SAT、FSAT
- SAT 問是否 $\phi$ 為 satisfiable
- FSAT 問是否 $\phi$ 為 satisfiable，可以則給出一組解
- 
- TSP(D)、TSP
- TSP(D) 問是否 $G$ 有長度不超過 $B$ 的 hamiltonian cycle
- TSP 問是否 $G$ 有長度不超過 $B$ 的 hamiltonian cycle，有則給出一組解
- 

## Randomized Computation
- 隨機演算法的分析
- 保證每次花固定時間，保證有一定機率 $p$ 可以找到正確解答
- 所以連續執行 $k$ 次，找不到解答的機率為 $(1-p)^k$
- 常用平行程式優化 [隨機平行法](https://pdfs.semanticscholar.org/a9ea/412e2a9a963dcf494710bd1e75cfd481d36a.pdf)
- **4 個最重要的隨機演算法**
- 1.Primality testing.
- 2.Graph connectivity using random walks.
- 3.Polynomial identity testing.
- 4.Algorithms for approximate counting.
- **Randomness Complexity Classes**
- **RP=Randomized Polynomial**：
- 定義：
- $x\in L$ $\iff$ 超過 $1/2$ 的 computation path 回答 yes
- $x\notin L$ $\iff$ 所有 computation path 回答 no
- 從回答的角度出發：
- **沒有 false positive**：回答正確就一定正確
- 存在 false negative：回答錯誤可能是正確
- $RP\subseteq NP$
- $RP\subseteq BPP$
- **ZPP=Zero Probability Polynomial**：
- 定義：$ZPP=RP\cap coRP$
- $L\in ZPP \iff$ $L$ 有一個 no false positive 及 no false negative 的演算法
- 反覆執行直到確認 $x\in L$
- 無法保證時間複雜度，但可以保證正確性
- **BPP=Bounded Probability Polynomial**
- 定義：
- $x\in L$ $\iff$ 超過 $3/4$ 的 computation path 回答 yes
- $x\notin L$ $\iff$ 超過 $3/4$ 的 computation path 回答 no
- $BPP=coBPP$
- Open：$NP$ 和 $BPP$ 是否有包含的關係。
- 
- **Bipartite Perfect Matching**
- 給定 bipartite graph $G=(U, V, E)$，問是否有 perfect matching
- 其實有 flow 的解法，底下用隨機演算法討論。
- **Lemma 66 (Schwartz, 1980)**：$p(x_1,x_2,...,x_n)$ 是 m 個變數、度數 d 、同餘 M 的多項式，則多項式的根 $\le mdM^{m-1}$ 個。
- 隨機猜一組 $(x_1,...,x_m)\in\{0,...,M-1\}^m$，是根的機率 $\le md/M$
- 
- 如果檢測發現是 0，可能只是猜對的，但猜對的機率 $\le md/M$
- **Proposition 65 (Edmonds, 1967)**：$G$ 有 perfect matching $\iff$ $det(A^G)$ is not identically 0。
- 先把 $G$ 轉乘矩陣形式 $A^G$。
- 一個實數矩陣的行列式，可以用高斯消去法在 $O(n^3)$ 算出。
- 
- 隨機猜一組 $(i_{11},...,i_{nn})\in\{0,...,M-1\}^m$，是根的機率 $\le n^2\cdot1 / 2n^2$
- 如果檢測發現是 0，可能只是猜對的，但猜對的機率 $\le 0.5$
- $FSAT$ 的隨機演算法：
- 
- 對於 $2SAT$ 來說：
- **Theorem 68**：給定 satisfiable 的 $2SAT$ 公式，若設定 $r=2n^2$，則有至少 $0.5$ 機率可以找到 satisfying $T$。
- 假設 $\hat{T}$ 為 satisfying assignment。
- 假設 $T$ 為一開始的 assignment。
- 定義 $t(i)$ 為如果 $T$ 和 $\hat{T}$ 有 $i$ 個變數不同，則用以上演算法期望要花幾個 iteration 才可以正確的 flip。
- $t(0)=0$
- $t(i)\le\frac{t(i-1)+t(i+1)}{2}+1$
- $t(n)=1+t(n-1)$
- 結論：$t(i)\le n^2$
- 所以設定 $r=2n^2$ ，可以使機率至少 $1/2$
- 如果設定 $r=2mn^2$ ，可以使機率至少 $1/2m$
- 如果設定 $r=2n^2$ ，但執行 $m$ 次，可以使機率至少 $1/2^m$
- **Primality Test**：
- **注意其實已經有多項式的方法了，底下算是多此一舉。**
- **Fermat Test**：
- 
- Carmichael numbers：
- $N$ 不是質數，但是 $a^{N-1}=1~mod~N$ 會通過測試
- 小於等於 $N$ 的 Carmichael numbers 約有 $N^{\frac{2}{7}}$ 個
- [**Euler Test**](https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%86%E5%88%99)：
- $a$ 是質數 $p$ 的**二次剩餘 quadratic residues**：
- $a$ 有平方根且 $gcd(a,p)=1$
- **Lemma 69 (Euler)** 給定質數 $p$：
- 如果 $a^{(p-1)/2}\equiv 1$，則 $a$ 有兩個相異平方根
- 如果 $a^{(p-1)/2}\equiv -1$，則 $a$ 沒有平方根
- 說明：
- 如果 $r$ 是生成元 $\rightarrow$ $r^{\frac{p-1}{2}}=-1$
- $a~有平方根~\iff~a=r^{2k}~\iff~a^{\frac{p-1}{2}}=1$
- $b~沒有平方根~\iff~b=r^{2k+1}~\iff~b^{\frac{p-1}{2}}=-1$
- 給定質數 $p$，定義 **Legendre symbol**：
- 
- **當 $p$ 是質數時，$(a|p)=a^{(p-1)/2}$ 表示 $a$ 是否有平方根**
- 舉例來說 $p=11,r=2$：
- $1^2=1,~2^2=4,~3^2=9,~4^2=5,~5^2=3$
- $6^2=3,~7^2=5,~8^2=9,~9^2=4,~10^2=1$
- $(1|11)=1,~(2|11)=-1,~(3|11)=1,~(4|11)=1,~(5|11)=1$
- $(6|11)=-1,~(7|11)=-1,~(8|11)=-1,~(9|11)=1,~(10|11)=-1$
- **特別定義：**
| $R=$ | $\{~q~,~2q~,~...~,~\frac{p-1}{2}q~\}$
| ----- | --------
| $R'=$ | $\{~1~,~2~,~...~,~\frac{p-1}{2}~\}$
- $R$ 中的每個數字都相異
- $R$ 中的任兩數字加總非零
- $R$ 中比 $(p-1)/2$ 還要大的數字有 $m$ 個
- 把那些數字變成負號而形成 $R'$
- **Lemma 70 (Gauss)**：給定兩質數 $p,q$，則 $(q|p)=(-1)^m$
- 把 $R'$ 所有數字相乘
- 看法一：$1\times 2\times 3\times ...(p-1)/2$
- 看法二：$q\times 2q\times 3q\times ...(p-1)q/2\times(-1)^m$
- 因此 $(q|p)=q^{(p-1)/2}=(-1)^m$
- **Lemma 71 (Legendre, 1785; Gauss)**：$(q|p)(p|q)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$
- 把 $R'$ 所有數字相加並 mod 2
- 看法一：$\sum\limits_{i=1}^{(p-1)/2}i$
- 看法二：$mp+\sum\limits_{i=1}^{(p-1)/2}(iq-p\lfloor\frac{iq}{p}\rfloor)$
- 因此：$m=\sum\limits_{i=1}^{(p-1)/2}\lfloor\frac{iq}{p}\rfloor~mod~2$
- 
- 定義：[**The Jacobi Symbol**](https://en.wikipedia.org/wiki/Jacobi_symbol) 為 Legendre symbol 的推廣
- $(a|m)=(a|p_1)(a|p_2)...(a|p_k)$，其中 $m=p_1...p_k$ 為 $m$ 的質因數分解
- $(1|m)=1$
- $(a|1)=1$
- **Theorem 72**：
- $\Phi(n)~有~generator~\iff~n~是~1,2,4,p^k,2p^k其中之一，其中~p~是奇質數$
- **Lemma 73**：
- 給定奇數 $N$，如果所有 $M\in\Phi(N)$ 都滿足 $(M|N)\equiv M^{(N-1)/2}$，則 $N$ 是質數。
- **Theorem 74 (Solovay & Strassen, 1977)**：
- 如果奇數 $N$ 是合數，則所有 $M\in\Phi(N)$ 滿足 $(M|N)\equiv M^{(N-1)/2}$ 的數字，不會超過一半。
- 演算法：
- 
- **隨機性相關的定理**：
- **Lemma 67 The Markov Inequality**：
- $x$ 是取值自正整數的隨機變數，則對任意 $k>0$，$p(x\ge kE[x])\le 1/k$
- 底下討論假定：$x_i$ 是滿足 $p$ 的機率為 $1$，$1-p$ 的機率為 $0$，且 $X=\sum x_i$。
- **Theorem 75、76**：對任意 $0\le\theta\le1$：
- $p(X\ge (1+\theta)pn)\le e^{-\theta^2pn/3}$
- $p(X\le (1-\theta)pn)\le e^{-\theta^2pn/2}$
- **Theorem 77**：對任意 $0\le\theta\le2$：
- $p(X\ge (1+\theta)pn)\le e^{-\theta^2pn/4}$
- $p(X\le (1-\theta)pn)\le e^{-\theta^2pn/4}$
- **Corollary 78**：$p(X\le n/2)\le e^{-\epsilon^2n/2}$
- 假定 $p=1/2+\epsilon$，$\theta=\frac{\epsilon}{1/2+\epsilon}$
- **Circuit Complexity**
- **Family of circuits** 是無限的序列 $C=(C_1,C_2,...)$，其中 $C_i$ 是 $i$ 個 input 的 boolean circuit
- $L$ 有 **polynomial circuit** $\iff$ 存在 $C=(C_1,C_2,...)$
- 每一個 $C_i$ 的大小最多為 $p(i)$
- $C_i$ decides $L\cap\{0,1\}^i$
- **Proposition 79**：每一個 languages $L$ $(decidable~or~not)$ 都有大小為 $2^{n+2}$ 的 **Circuits**
- 每一個 $C_i$ 的大小最多為 $2^{i+2}$
- $s(n)=4+2s(n-1)\le 2^{n+2}$
- **Proposition 80**：每一個 languages $L\in P$ 都有 **Polynomial Circuits**
- 存在多項式時間 $p(n)$ $DTM$ decides $L$
- 用大小 $O(p(n)^2)$ 的 circuit 來模擬 $DTM$。
- **Corollary**：存在 undecidable language ，有 polynomial circuit。
- 假設 $L$ undecidable，$U=\{1^n|n_2\in L\}$
- $U$ undecidable，但是 $U$ 有 polynomial circuit
- **Theorem 81 (Adleman, 1978)**：每一個 languages in $BPP$ 都有 polynomial circuit。
- 假設 $L\in BPP$，$N$ 是對應的 $NTM$ 執行時間為 $p(n)$
- 假設 input $x$ 長度為 $n$ ，我們要構造出對應的 $C_n$
- 存在 $A_n=\{p_1,...,p_{12(n+1)}\}$，對於所有長度 $n$ 的 input $x$ ，$bad$ 的路徑都不超過一半。
- 對於一個特定 $x$ ，誤判的機率 $e^{-m/12}=2^{-(n+1)}$
- $p(X\ge (1+\theta)pn)\le e^{-\theta^2pn/3}$
- $p=\frac{1}{4}、\theta=1$
- 對於所有可能 $x$ ，誤判的機率 $\le 2^n2^{-(n+1)}=2^{-1}$
- $A_n$ 不誤判的機率 $\ge 0.5>0$

## Cryptography
- **密碼學基礎**
- 加密：$y=E(e,x)$
- 解密：$x=D(d,y)$
- 公開的部分：E、D、y、e
- 隱藏的部分：x、d
- Perfect secrecy：攻擊者就算知道密文與演算法，仍然對明文的機率分布一無所知
- Informationally secure：滿足條件
- Computationally secure：理論上可能不滿足，但實務上是
- 一個系統是 Perfect secrecy $\iff$
- 1.每個 key 都是隨機被選出
- 2.給定明文以及密文，存在唯一的 key 使得 $E(e,x)=y$
- EX：One-Time Pad 一次性密碼本
- **Public-Key Cryptography 公鑰密碼學**
- 公鑰：e
- 私鑰：d
- 傳訊息：
- 加密：$y=E(e,x)$
- 解密：$x=D(d,y)$
- 數位簽章：
- 簽章：$(x,y=D(d,x))$
- 驗章：檢查 $E(e,y)==x$
- 複雜度分析：
- 破密 $\in NP$
- **Blind Signature 盲簽章**
- 性質：
- 簽名者簽名當下，消息內容不可見
- 簽名訊息被公布後，大家知道簽名者簽名，但簽名者不可追蹤
- 演算法：
- 1.盲化：$x'=x\cdot r^e$
- 2.簽章：$y'=x'^d$
- 3.解盲：$y=y'\cdot r^{-1}$
- 根據此過程：
- $y=x^dr^{ed}r^{-1}=x^d$
- 驗章：檢查 $y^e==x$
- 簽章人在看到 $(x,y)$ 時，不知道和 $x'$ 有關
- 應用：
- 匿名投票：使用者投票之後盲化給主辦單位簽章，解盲後再投入票匭。
- **One-Way Functions 單向函數**
- 定義：$f$ 是 One-Way Function $\iff$
- 1.一對一函數
- 2.$|x|^{1/k}\le|y|\le|x|^k$
- 3.$f$ 可以在多項式時間算出
- 4.$f^{-1}$ 不行在多項式時間算出
- 目前還沒有任何 function 被證明是 one-way function
- 如果 one-way function 存在，則 $P\ne NP$ [ref](https://crypto.stackexchange.com/questions/39878/how-to-show-that-a-one-way-function-proves-that-p-%E2%89%A0-np)
- 如果 $P\ne NP$，仍然不知 one-way function 是否存在
- 實務上接近 one-way function
- 離散對數：$f(x)=g^x~mod~p$
- RSA：$f(x)=x^e~mod~pq$ 其中 $e$ 和 $\phi(pq)$ 互質
- QRA：$f(x)=x^2~mod~pq$
- **Key Exchange**
- 演算法：
- 公開：$g$ 是 $p$ 的 primitive root
- Alice send：$g^a~mod~p$
- Bob send：$g^b~mod~p$
- 兩人得到密鑰：$g^{ab}~mod~p$
- Computational Diffie-Hellman Assumption (CDH)：
- Diffie-Hellman problem 被認為是無法有效率的解出
- **RSA**
- 演算法：
- 公鑰：$(n=pq,e)$，私鑰：$d$
- $e$ 和 $\phi(pq)$ 互質
- $ed=1~mod~\phi(pq)$
- 加密：$y=x^e$ mod $pq$
- 解密：$x=y^d$ mod $pq$
- 正確性：
- $x^{ed}=x\cdot x^{k(p-1)(q-1)}$
- 不管 $x$ 和 $p$ 是否互質，$x^{ed}=x~mod~p$
- 不管 $x$ 和 $q$ 是否互質，$x^{ed}=x~mod~q$
- 因此根據中國剩餘定理，$x^{ed}=x~mod~pq$
- 困難性：
- 因數分解 → 計算 $\Phi(x)$ → 破解 RSA
- **Probabilistic Encryption**
- **Lemma 82**：令 $n=pq$。 $y$ 是 $n$ 的二次剩餘 $\iff$ $(y|p)=(y|q)=1$
- $(r|p)=1,~~(r|q)=1$：$r$ 是 $n$ 的二次剩餘
- $(r|p)=-1,~~(r|q)=-1$：$r$ 不是 $n$ 的二次剩餘
- $(r|p)=1,~~(r|q)=-1$：$r$ 不是 $n$ 的二次剩餘
- $(r|p)=-1,~~(r|q)=1$：$r$ 不是 $n$ 的二次剩餘
- 根據 QRA ，檢測 $y$ 是 $n$ 的二次剩餘很困難。但若知道 $p$、$q$，就可直接由上式檢測。
- $(r|p)$ 可以用公式化簡，但 $(r|pq)$ 不行
- 演算法(每個 bit 要傳送一個數字)：
- 1.Bob 公布：$n=pq$，二次非剩餘 $y$ 滿足 $(y|n)=1$
- 2.Alice 想要傳送字串 $b_1...b_n$
- 3.Alice 每次隨機挑選 $r$
- $b_i==1$：傳送 $r^2~mod~n$ → 二次剩餘
- $b_i==0$：傳送 $r^2y~mod~n$ → 二次非剩餘
- 4.Bob 每次收到訊息 $r$
- $(r|p)=(r|q)=1$：$b_i==1$
- 其他三種情況：$b_i==0$
- **Interactive Proof 交互式證明** [ref](https://zh.wikipedia.org/wiki/%E4%BA%A4%E4%BA%92%E5%BC%8F%E8%AF%81%E6%98%8E%E7%B3%BB%E7%BB%9F)
- Interactive Proof System
- Prover：
- 存在誠實的 Prover 可以成功說服 Verifier
- Exponential-time algorithm $A$
- 可以看到 input x 以及雙方曾經溝通的訊息
- Verifier：
- 所有的 Verifier 都是誠實的，但要提防不誠實 Prover
- Probabilistic polynomial time algorithm $B$
- 可以看到 input x 以及雙方曾經溝通的訊息，此外每次溝通可產生只有自己可見的 random bit $r_i$
- System $(A,B)$ decides language $L$
- $x\in L$：$(A,B)$ 接受 $x$ 的機率至少 $1-\frac{1}{2^{|x|}}$
- $x\notin L$：對任意的 $A'$, $(A',B)$ 接受 $x$ 的機率最多 $\frac{1}{2^{|x|}}$
- $IP$ ： 可以被 Interactive Proof Systems 所 decide 的 language class
- $NP\subseteq IP$：prover 猜測一條路徑，verifier 決定該路徑的 output。
- $BPP\subseteq IP$：verifier 忽略 prover，根據 Chernoff bound
- $IP=PSAPCE$
- **Graph Isomorphism**：在 $NP、IP$ 裡，不太可能 $NP-complete$
- **Graph NonIsomorphism**：在 $coNP、IP$ 裡，不太可能 $coNP-complete$
- 1.Victor 傳送 $(G_1,H)$ ，其中 $H$ 是隨機圖 $G_i$ 隨機 relabel
- 2.Peggy 用指數演算法，判斷 $(G_1,H)$ 是否同構
- 同構 → 回傳 $j=1$
- 不同 → 回傳 $j=2$
- 3.Victor 判斷
- $i==j$ → 接受 ( 認為$(G_1,G_2)$不同構 )
- $i~~!=j$ → 拒絕 ( 認為$(G_1,G_2)$同構 )
- **Zero Knowledge Proof 零知識證明** [ref](https://en.wikipedia.org/wiki/Zero-knowledge_proof)
- 基本想法：
- Prover 告訴 Verifier 他知道答案 ( $x\in L$ )，卻不告訴 Verifier 答案本身的任何資訊 ( Why $x\in L$ ? )
- Verifier 在溝通知道 Prover 知道答案 ( $x\in L$ ) 之後，無法說服其他第三方自己知道答案
- Prover 能夠說服 Verifier 的原因，不只是因為它們交換訊息的內容本身，而是交換訊息的過程是 "on line"
- 一個 $L$ 的交互是證明協議 $(P,V)$ 有零知識證明 $\iff$
- 1.每一個 verifier $V'$，都存在演算法 $M$ 期望執行時間為多項式
- 2.$M$ 在任何 $x\in L$ 上執行的結果，和 $(P,V')$ 通道上的傳訊，機率分布一樣
- 舉例：Quadratic Residuacity
- 問題： Prover 證明 $x\in Z_n^*$ 是 quadratic residue
- **Corollary 83**：在 mod $n=pq$ 下，
- 二次剩餘乘以二次剩餘，為二次剩餘
- 二次剩餘乘以非二次剩餘，為非二次剩餘
- 演算法：假設 $u$ 是 $x\in Z_n^*$ 的平方根
- 1.Peggy 自己挑選 $y=v^2~mod~n$
- 2.Victor 傳送 random bit $i$
- 3.Peggy 傳送 $z=u^iv$
- 4.Victor 檢查 $z^2=x^iy$
- 分析：$(y,i,z)$ 可以被 generate without Peggy
- 先隨機設定 $z、i$，則 $y=z^2x^{-i}$
- 但只要是 "on line" 的產生，就可以保證 Zero Knowledge
- 舉例：3 Colorability
- 問題：Prover 證明圖 $G=(V,E)$ 是 3-colorable
- 演算法：
- 1.Peggy 隨意將圖 $G$ 的 3-coloring relabel
- 2.Peggy 將每個點加密傳給 Victor
- 3.Victor 隨機挑選 $e\in E$ 並傳送
- 4.Peggy 回答兩端點的正確顏色
- 5.Victor可以檢查加密是否正確、顏色是否相異
- Commitment Scheme 信息提交協議
- Committer 事先宣布自己選擇的加密值，直到對方選擇之後，才揭露 committer 真正的選擇
- **Binding**
- Committer 不可以改變心意
- Perfect Binding：一對一函數
- **Concealing**
- 對方不可以是先知道 Committer 的選擇
- Perfect Concealing：多對一函數
## Approximability
- 一些定義：
- 在最佳化問題中，給定一個 instance $x$，$F(x)$ 表示其 feasible solutions
- 每一個 feasible solution $s\in F(x)$，都有一個 cost $c(s)\in Z^+$
- $M$ 是一個 $\epsilon$-approximation algorithm，$0\le\epsilon\le 1$
- 最小值問題：$\frac{c(M(x))-OPT(x)}{c(M(x))}\le\epsilon$ ， $c(M(x))\in[OPT,\frac{OPT}{1-\epsilon}]$
- 最大值問題：$\frac{OPT(x)-c(M(x))}{OPT(x)}\le\epsilon$ ， $c(M(x))\in[(1-\epsilon)OPT,OPT]$
- Approximation Thresholds：最大的 lower bound for $\epsilon$
- Approximation Ratio：定義為 $r=\frac{c(M(x))}{OPT(x)}$
- 最小值問題：$\epsilon=1-\frac{1}{r}$-approximation algorithm
- 最大值問題：$\epsilon=1-r$-approximation algorithm
- $Vertex~Cover$：$\epsilon=0.5$
- 問題：給定 $G = (V,E)$，挑出一個最小的點集合 $C$，使得每個邊都有端點在 $C$ 裡
- 每次挑 degree 最大的點：Approximation Ratio = $\theta(logn)$
- 每次挑圖上還未覆蓋的邊：**0.5**-Approximation Algorithm
- Approximation Threshold 被證明至少 $1-(10\sqrt{25}-21)^{-1} \approx 0.2651$ [ref](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/vc.pdf)
- $MAX~SAT$：$\epsilon=1-\min\limits_{p(\phi_i)>0}p(\phi_i)$
- 問題：給定一些 expressions ，$\phi_1,...,\phi_m$，找出 truth assignment 可以滿足最多的 expressions
- 假測 $\phi_i$ 有 $k_i$ 個變數， $2^{k_i}$ 個填法之中，有 $s_i$ 種是 true
- $p(\phi_i)=s_i/2^{k_i}$
- 演算法：從 $x_1$ 直到 $x_n$，greedy 的決定變數 $x_i$ 的值
- $p(\Phi)$$\le p(\Phi[x_1=?])\\\le p(\Phi[x_1x_2=??])\\\le p(\Phi[x_1...x_n=?...?])$
- Approximation Ratio $\ge\frac{p(\Phi)}{\sum\limits_{p(\phi_i)>0}1}\ge\min\limits_{p(\phi_i)>0}p(\phi_i)$
- $MAX~CUT$：$\epsilon=0.5$
- 問題：把圖 $G=(V,E)$ 的點分成兩區，使得跨越的邊越多越好。
- 演算法：如果圖上有一個點，使得換到另外一區可以更好，則換過去
- 
- $2e_{11}+e_{12}\le e_{13}+e_{14}$
- $\rightarrow e_{12}\le e_{13}+e_{14}$
- $\rightarrow e_{12}+e_{34}\le e_{13}+e_{14}+e_{23}+e_{24}$
- $\rightarrow e_{14}+e_{23}+e_{12}+e_{34}\le 2(e_{13}+e_{14}+e_{23}+e_{24})$
- $TSP$：不存在近似演算法，threshold = 1
- 假設有 $\epsilon$ 近似演算法，給定 hamiltonian cycle 的 input $G=(V,E)$
- 建構對應 $TSP$ 的 input：有 $V$ 個城市
- 如果原圖有邊，則 $d_{ij}=1$
- 如果原圖沒邊，則 $d_{ij}=\frac{|V|}{1-\epsilon}$
- 如果 $\epsilon$ 近似演算法回傳值是 $V$，則對應的路徑即為原圖的 hamiltonian cycle
- 如果 $\epsilon$ 近似演算法回傳值大於 $V$，則大於 $\frac{|V|}{1-\epsilon}$
- 根據 $c(M(x))\in[OPT,\frac{OPT}{1-\epsilon}]$，有 $\frac{|V|}{1-\epsilon}<c(M(x))\le \frac{OPT}{1-\epsilon}$
- 因此 hamiltonian cycle 不存在
- $Metric~TSP$：$\epsilon=0.5$
- 演算法：
- $T$ 是圖上的 MST
- $T'$ 是 $T$ 的 duplicate
- $C$ 是 $T'$ 上的 Euler cycle，並且移除從重複的 node
- 正確性：
- $c(C)\le c(T')$：因為是 Metric 圖上的 shortcut
- $c(T')=2c(T)$：因為是 duplicate
- $c(T)\le c(C_{opt})$：因為 $C_{opt}$ 任意移除一個邊即為 spanning tree
- $Metric~TSP$：$\epsilon=1/3$
- 演算法：
- $T$ 是圖上的 MST
- $M$ 是 $T$ 上 odd degree 點所形成的 min cost perfect matching
- $G''=T\cup M$
- $C$ 是 $G''$ 上的 Euler cycle，並且移除從重複的 node
- 正確性：
- $c(M)\le 0.5 c(C')\le 0.5c(C_{opt})$：
- $C'$ 是 $C_{opt}$ 在 odd degree 點的 shortcut
- $c(T)\le c(C_{opt})$：因為 $C_{opt}$ 任意移除一個邊即為 spanning tree
- $c(C)\le c(M)+c(T)\le \frac{3}{2}c(C_{opt})$
- $Knapsack$：$PTAS$，threshold = 0
- 問題：給定 $n$ 個物品，每個有重量 $w_i$ 和價值 $v_i$，在重量限制 $W$ 下，求最大價值
- 演算法：
- 假設 $V$ 為所有物品中的最高價值，則用 DP 可以設計 $O(n^2V)$ 的正確演算法
- 原問題物品價值為 $v_i$，最佳解為 $S$
- 新問題物品價值為 $v_i'=\lfloor\frac{v_i}{k}\rfloor$，最佳解為 $S'$
- 關係式：
- $\sum\limits_{S}v_i\ge\sum\limits_{S'}v_i$：因為原問題最佳解為 $S$
- $\sum\limits_{S'}v_i'\ge\sum\limits_{S}v_i'$：因為新問題最佳解為 $S'$
- $\frac{v_i}{k}-1 < v_i' \le\frac{v_i}{k}$
- $v_i-k < v_i'*k \le v_i$
- 最佳解為：$\sum\limits_{S}v_i$
- 演算法解為：$\sum\limits_{S'}v_i$
- 正確性：
- $\sum\limits_{S'}v_i\ge\sum\limits_{S'}v_i'*k\ge\sum\limits_{S}v_i'*k\ge\sum\limits_{S}(v_i-k)\ge\sum\limits_{S}v_i-nk$
- 演算法解 $\ge$ 最佳解 $-~nk$
- $\epsilon=\frac{最佳解-演算法解}{最佳解}\le\frac{nk}{V}$
- 可以取 $k=\frac{V}{n}\epsilon$，即為一般 $\epsilon$ 近似演算法
- $k$ 取越大，演算法速度越快，但誤差也越大
## On P vs. NP
- Monotone circuits：沒有 not gate 的 circuit
- Monotone problem：把 Input 的任何一個 bit 從 false 變成 true，答案不會從 true 變成 false。
- HAMILTON PATH、CLIQUE
- $CLIQUE_{n,k}$：$n$ 個點的圖中，是否存在大小為 $k$ 的 clique
- Crude Circuit：$CC(X_1,...,X_m)$
- 每一個 $X_i\subseteq V$ 是一個點的子集合
- 每一個 $X_i\subseteq V$ 測試是否 $X_i$ 形成一個 clique
- 給定 $n$ 個點的特殊圖：
- Positive Examples：圖上只有 $\frac{k^2-k}{2}$ 個邊，恰好為一個大小為 $k$ 的 clique
- Negative Examples：將圖上的 $n$ 個點任意用 $k-1$ 個顏色圖色，將不同顏色的點對建立邊，則此圖必定不存在大小為 $k$ 的 clique
- **Lemma 86**：把 $q$ 個球隨機丟到 $N$ 個桶子中，發生衝突的機率**最多** $\frac{q(q-1)}{N}$
- $1-\frac{N}{N}\times...\times\frac{N-q+1}{N}\le1-q\frac{N-q+1}{N}\le q-q\frac{N-q+1}{N}=\frac{q(q-1)}{N}$
- **Lemma 87**：若 Crude Circuit：$CC(X_1,...,X_m)$ decides $CLIQUE_{n,k}$，則 $m\ge n^{n^{1/8}/20}$
- Sunflowers：$\{P_1,...,P_p\}$
- 有 $p$ 個 petals
- 任兩個 set 有相同的交集：core
- **Lemma 88**：如果 $Z$ 有超過 $M=(p-1)^l(l-1)!$ 個集合，每個集合的元素最多有 $k$ 個，則 $Z$ 一定有 $p$ 個 petals 的 sunflower
- 數學歸納法
- Plucking：
- 把 sunflower 的 $p$ 個集合用一個 core 取代
- $pluck(Z)$ 持續做 plucking 的動作，直到大小不超過 $M$
- 注意 $pluck(Z)$ 不唯一。
- **Theorem 89**：存在 $c$，若 monotone circuit decides $CLIQUE_{n,k}$ 其中 $k=n^{1/4}$，則它的大小至少為 $n^{cn^{1/8}}$
- **目標：任意給定 $CLIQUE_{n,k}$ 的 monotone circuit，我們都可以用 crude ciruit 近似它，近似的過程每一步驟會產生小錯誤，但是最後得 circuit 會有大量錯誤**
- Crude Circuit：$CC(X_1,...,X_m)$
- $X_i\subseteq V$
- $|X_i|\le l=n^{1/8}$
- $m\le M=(p-1)^ll!=(n^{1/8}logn-1)^ll!$
- **Lemma 90**：$CC(pluck(X\cup Y))$ 不產生 false negatives
- **Lemma 91**：$CC(pluck(X\cup Y))$ 產生的 false positives 最多 $\frac{2M}{p-1}2^{-p}(k-1)^n$
- **Lemma 92**：Approximate AND 產生的 false positives 最多 $M^22^{-p}(k-1)^n$
- **Lemma 93**：Approximate AND 產生的 false negatives 最多 $M^2C_{k-l-1}^{n-l-1}$
- **Lemma 94**：
- **Lemma 95**：
- 每一個 Approximate 過程產生的 false positives 最多 $M^22^{-p}(k-1)^n$
- 每一個 Approximate 過程產生的 false negatives 最多 $M^2C_{k-l-1}^{n-l-1}$
- **Lemma 96**：最後的 circuit 必定是以下其一
- 總是回答 false
- 對於 negative examples 有超過一半都會回答 true
- 分析：
- positive examples：有 $C_k^n$ 個
- $\frac{C_k^n}{M^2C_{k-l-1}^{n-l-1}}\ge\frac{1}{M^2}(\frac{n-l}{k})^l\ge n^{n^{1/8}/12}$
- negative examples：有 $(k-1)^n$ 個
- $\frac{(k-1)^n}{M^22^{-p}(k-1)^n}\ge\frac{2^{p-1}}{M^2}\ge n^{n^{1/8}/3}$