時間複雜度

測量複雜度

Worst-case analysis

Average-case analysis

定義一個M是Deterministic Turing Machine並且會根據輸入決定停止

規範M的執行時間或者時間複雜度可以表示成一個function $f:N \rightarrow N$ ，其中 $f(n)$ 是指M輸入長度n的最大步驟數量
如果 $f(n)$ 是M的執行時間，可以表示M執行 $f(n)$ 的時間並且稱M是一個 $f(n)$ 時間的Turing Machine

Big-O以及Small-o漸進符號

定義： $f(n) = O(g(n))$ ，如果存在一個正整數c(通常是個常數)以及 $n_{0}$ 使得任何的 $n \geq n_{0}, f(n) \leq cg(n)$
範例： $f(n) = 5n^{3}+2n^{2}+22n+6$ , $f(n) = O(n^{4}), f(n) = O(n^{3})$
顧名思義就是存在一組時間複雜度是目前 $f(n)$ 的執行時間上限
定義： $f, g: N \rightarrow R^{+}$ , 表示 $f(n) = o(g(n))$ if

$\underset{n \rightarrow \infty}{\operatorname{lim}}\frac{f(n)}{g(n)} = 0$

範例： $\sqrt(n) = o(n), n^{2} = o(n^{3}), nloglogn = o(nlogn)$
定義： $t: N \rightarrow N$ 作為一個function
$TIME(t(n))$ : 時間複雜度類別 = {L | L是一個language可以被 $O(t(n))$ 時間的Turing Machine給決定}
不同的模型設計之下會有不同的複雜度關聯
定理： $t(n):$ 一個function $\geq n$ ，任何 $t(n)$ 時間的Multi-tape Turing Machine等同於 $O(t^{2}(n)$ 時間的單一tape Turing Machine
定理： $t(n):$ 一個function $\geq n$ ，任何 $t(n)$ 時間的Non-deterministic single-tape Turing Machine等同於 $2^{O(t(n))}$ 時間的deterministic single-tape Turing Machine

P類別

P是指language的類別能夠被deterministic single-tape Turing Machine在多項式時間(polynomial time)內被決定(decidable)，換言之可以表示成：

$P = \bigcup_{k}TIME(n^{k})$

舉例來說：
有一組 $PATH$ = {< $G, s, t$ >| $G$ 是一個有向圖其中存在一條有向路徑可以從 $s$ 到達 $t$ }

定義： $PATH \in P$
另外像是 $RELPRIME$ = {< $x, y$ >| $x, y$ 為互質}，也同樣定理： $RELPRIME \in P$

NP類別

Hamiltonian path是一組有向圖 $G$ 存在一條有向路徑可以從 $s$ 走到 $t$ 且每個點只經過一次
$HAMPATH$ = {< $G, s, t$ >|G是一個有向圖存在一條Hamiltonian path從 $s$ 到 $t$ }

可以觀察到存在指數時間(exponential time)的演算法來解決HAMPATH問題，而要驗證HAMPATH問題的話只要給路徑的點跟線就可以在多項式時間裡驗證
$COMPOSITES$ = { $x| x = pq$ , 對於所有的整數 $p, q > 1$ }，找兩個整數相乘在一起的稱作合成數
$12653 = 123 \times 111$ ，可以看到如果有給 $p,q$ 這兩個通常稱作certificate(證據)的話就可以在多項式時間內驗證合成數
但要注意也並不是每個問題都能夠在多項式時間裡驗證
定義：存在一個演算法針對language A的驗證者(verifier) V，其中 $A = \{ \omega | V 接受 <\omega, c>$ 針對某些字串 $c\}$

一個多項式時間的verifier執行驗證長度 $\omega$ 的字串在多項式時間內

一個language A是多項式可驗證的話代表這是一個多項式時間的verifier

一個verifier使用額外的資訊 $c$ 來驗證字串 $\omega$ 屬於A的集合成員

C: 證據(certificate)或者可以用來證明屬於A的集合成員
定義：NP是一個擁有多項式時間驗證者的language集合，代表可以在多項式時間內驗證完，但不保證能夠在多項式時間內找出答案
NP: Non-deterministic Polynomial time

定義： $NTIME(t(n)) = \{L|L$ 是一個language可以被Non-Deterministic TM在 $O(t(n))$ 時間內被決定(decided) $\}$
定理：一個language如果在NP裡面的話若且唯若會被Non-deterministic polynomial time Turing Machine被決定(decided)
證明：
$(\Rightarrow)$ ：使 $A \in NP$ 以及證明A會被NTM N所決定(decided).
根據NP的定義讓V是一個多項式時間驗證者針對A
首先假設V可以對輸入長度n的執行驗證時間在 $n^{k}$ 的時間內
開始來建構這個N：
N = 可以輸入長度n的字串 $\omega$

Non-deterministically去猜長度 $n^{k}$ 的字串c
V執行驗證猜的這個字串 $<\omega, c>$
如果V可以接受，輸出ACCEPT，反之亦然，輸出REJECT

$(\Leftarrow)$ ：假設A可以被NTM N在多項式時間內所決定(decided)並且建構出多項式時間驗證者V功能如下：

模擬N輸入 $\omega$ ，處理c的每一個符號像是Non-deterministic的方法一樣
如果Non-deterministic的branch可以accept，輸出ACCEPT，反之輸出REJECT

推論：

$NP = \bigcup_{k}NTIME(n^{k})$

NP問題範例

定義：clique是一個無向圖，而這個圖內每兩個點(node)必定存在一條邊(edge)

一個k-clique代表clique裡面包含k個點(nodes)

定義：CLIQUE = {< $G, k$ >| $G$ 是一個無向圖擁有k-clique}

定義：CLIQUE屬於NP

證明：
N = 輸入 $<G, k>, G$ 是一個圖：

Nondeterministically猜一組 $G$ 裡有 $k$ 個nodes的子集合 $c$
測試 $G$ 是否包含所有的邊都連接這條 $c$
如果包含的話輸出ACCEPT，反之輸出REJECT

定義：SUBSET-SUM = { $<S, t>|S = \{x_{1},…,x_{k}\}$ 以及對於某些 $\{y_{1},….,y_{k}\}\subseteq S,\sum y_{i}=t$ }
例如：<{4, 11, 16, 21, 27}, 25} $\in$ SUBSET-SUM, $\because 4+21 = 25$ ，可以注意到 $S$ 跟 $\{y_{1},…..,y_{k}\}$ 可以是多組子集合定義：SUBSET-SUM $\in$ NP 證明：N = 輸入 $<S, t>$