---
# System prepended metadata

title: 課程｜資訊工程理論
tags: [課程]

---

# 資訊工程理論


## 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.
    - ![](https://i.imgur.com/q2IrVI6.png)
    - $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$
    - ![](https://i.imgur.com/ZSY4uYz.png)
        - 定義 $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$
        - ![](https://i.imgur.com/DKGSEaM.png)
        - 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$
        - ![](https://i.imgur.com/pbWU51s.png)![](https://i.imgur.com/RSzf59P.png)
        - 這是一個 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：**
    - ![](https://i.imgur.com/3jQPtO8.png)
    - 假設時間是 $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$ 建立一個邊
            - ![](https://i.imgur.com/GWHQhlc.png)
            - 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$
                    - ![](https://i.imgur.com/cxoSPrx.png)
                - 證明： $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/)
            - ![](https://i.imgur.com/UsXwHUR.png)
            - ![](https://i.imgur.com/vn83D72.png)
            - $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}$
            - ![](https://i.imgur.com/5dgVI36.png)
            - $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)
            - ![](https://i.imgur.com/UNsVPgK.png)
        - 相關問題：
            - 給定目標 $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)
        - ![](https://i.imgur.com/bFNA4tO.png)
    - $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，可以則給出一組解
    - ![](https://i.imgur.com/5T2c1T8.png)
- TSP(D)、TSP
    - TSP(D) 問是否 $G$ 有長度不超過 $B$ 的 hamiltonian cycle
    - TSP 問是否 $G$ 有長度不超過 $B$ 的 hamiltonian cycle，有則給出一組解
    - ![](https://i.imgur.com/Hy19IQb.png)

## 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$ 是否有包含的關係。
    - ![](https://i.imgur.com/zpsUtWA.png)
- **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$
        - ![](https://i.imgur.com/YyTK02s.png)
        - 如果檢測發現是 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)$ 算出。
        - ![](https://i.imgur.com/pDEU6eZ.png)
        - 隨機猜一組 $(i_{11},...,i_{nn})\in\{0,...,M-1\}^m$，是根的機率 $\le n^2\cdot1 / 2n^2$
        - 如果檢測發現是 0，可能只是猜對的，但猜對的機率 $\le 0.5$
- $FSAT$ 的隨機演算法：
    - ![](https://i.imgur.com/PcydD3X.png)
    - 對於 $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**：
        - ![](https://i.imgur.com/mjwzGvU.png)
        - 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**：
            - ![](https://i.imgur.com/pZ0vi3O.png)
            - **當 $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$
            - ![](https://i.imgur.com/WuxtcPo.png)
        - 定義：[**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}$ 的數字，不會超過一半。
        - 演算法：
            - ![](https://i.imgur.com/WEIg6D0.png)
- **隨機性相關的定理**：
    - **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)$ 的點分成兩區，使得跨越的邊越多越好。
    - 演算法：如果圖上有一個點，使得換到另外一區可以更好，則換過去
    - ![](https://i.imgur.com/sviJn8H.png)
    - $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}$
