時間複雜度

目錄

• 測量複雜度
• Big-O以及Small-o漸進符號
• P類別
• NP類別
• NP問題範例

測量複雜度

• Worst-case analysis

• Average-case analysis

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

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

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

定義：，如果存在一個正整數c(通常是個常數)以及使得任何的
範例：,
顧名思義就是存在一組時間複雜度是目前的執行時間上限
定義：, 表示 if

   

範例：
定義：作為一個function
: 時間複雜度類別 = {L | L是一個language可以被時間的Turing Machine給決定}
不同的模型設計之下會有不同的複雜度關聯
定理：一個function ，任何時間的Multi-tape Turing Machine等同於時間的單一tape Turing Machine
定理：一個function ，任何時間的Non-deterministic single-tape Turing Machine等同於時間的deterministic single-tape Turing Machine

P類別

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

   

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

定義：
另外像是 = {<>|為互質}，也同樣定理：

NP類別

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

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

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

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

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

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

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

1. Non-deterministically去猜長度的字串c
2. V執行驗證猜的這個字串
3. 如果V可以接受，輸出ACCEPT，反之亦然，輸出REJECT

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

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

推論：

   

NP問題範例

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

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

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

• 定義：CLIQUE屬於NP

證明：
N = 輸入是一個圖：

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

定義：SUBSET-SUM = {以及對於某些}
例如：<{4, 11, 16, 21, 27}, 25} SUBSET-SUM, ，可以注意到跟可以是多組子集合 定義：SUBSET-SUM NP 證明：N = 輸入

1. Non-deterministically猜一個S裡面的子集合c
2. 測試是否是一個可以加總出的集合
3. 如果以上兩點都成功就輸出ACCEPT，反之輸出REJECT

所以我們稍微做個小結

P = 問題能夠被快速(polynomial)決定(decided)出來結果的language類別

NP = 問題能被快速(polynomial)驗證(verified)出來結果的language類別

而電腦科學從1950年開始發展至今一直都還沒有嚴謹證明出來的Open Problem

   

P到底等不等於NP?