跳到正文

CSCI3360

計算複雜度導論

計算模型、非確定性與歸約、空間複雜度、隨機計算、電路與計數、多項式層級、互動證明及機率可檢驗證明。

10 章 · 33 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 33 節已標記完成

下一節: 隨機化計算與放大

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI3360 筆記裏的內容

定理卡
94
定義
50
反例
33
概念視角
17
思想史
1
證明透視
33

有思想史的節

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 94 · 定義 50 · 反例 33 · 概念視角 17 · 思想史 1 · 證明透視 33

這些思想史還沒有放上時間線。

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 4 節

隨機化複雜度

公平隨機位元、RP、BPP、放大、零錯誤計算與恆等測試

定理 10 · 定義 4反例 4視角 1證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    隨機化計算與放大

    定義單側錯誤與雙側錯誤,並利用獨立重複證明多數放大。

  2. 1.2

    零錯誤隨機計算

    以有界截斷及獨立單側算法證明零錯誤類別的刻畫。

  3. 1.3

    方差界與隨機恆等檢驗

    證明方差放大界,並分析使用公平位元的多項式恆等測試。

  4. 1.4

    仿射雜湊與有限獨立性

    證明質數域上的兩兩獨立性,並區分雜湊值獨立與碰撞事件獨立。

第 2 章 · 4 節

非確定性與歸約

NP 與 coNP 證明、多項式歸約,以及 3-SAT 到 CLIQUE 的證明。

定理 10 · 定義 11反例 5視角 3證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    非確定性、歸約與完全性

    區分 NP 與 coNP 證明並證明圖歸約,以 3-SAT 困難性為背景。

  2. 2.2

    把驗證者轉化為可滿足性實例

    為有界計算構造布爾電路,並證明電路可滿足性是 NP 完全的。

  3. 2.3

    閘約束、SAT 與三文字子句

    用輔助變量保持電路的共享結構,並通過證明兩個方向與規模界來證明可滿足性歸約。

  4. 2.4

    見證搜尋、判定與類 DP

    由判定查詢中復原多項式長度的見證,並謹慎地結合 NP 與 coNP 條件。

第 3 章 · 7 節

空間與可達性

空間模型、有向可達性與組態計數。

定理 21 · 定義 14反例 7視角 4證明透視 7

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    空間與有向可達性

    定義對數空間計算,證明有向可達性屬於 NL 及 NL 包含於 P。

  2. 3.2

    Savitch 定理:模擬非確定性空間

    透過隱式組態圖證明一般的平方空間模擬,解釋多項式空間類相等及歸約的複合。

  3. 3.3

    量化布爾公式、空間與互動證明

    證明 TQBF 為 PSPACE 完全,並證明互動證明具有多項式空間上界。

  4. 3.4

    可達性的完全性與中點遞歸

    構造組態圖歸約並分析確定性的中點遞歸。

  5. 3.5

    為甚麼非確定性對數空間在補運算下封閉

    利用歸納計數在對數空間內驗證不可達性。

  6. 3.6

    2-SAT、蘊含圖與 NL 完全性

    證明蘊含圖判據,並用對數空間可達性刻畫二文字可滿足性。

  7. 3.7

    確定性空間層級

    利用組態數目界限與有界模擬,證明更多的空間可判定嚴格更多的語言。

第 4 章 · 4 節

計算與模型

判定問題、資源界限、編碼與不可判定性。

定理 10 · 定義 5反例 4視角 1思想史 1證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    計算、資源與對角化

    定義計算資源,並用計數與對角化研究可判定性。

  2. 4.2

    用一條紙帶模擬多條紙帶

    區分舊、新讀寫頭標記,證明固定紙帶數的多項式時間穩健性。

  3. 4.3

    確定性時間層級定理

    利用帶時鐘的通用模擬與對角化方法,分離確定性時間界。

  4. 4.4

    神諭世界與相對化的局限

    構造使 P 與 NP 問題得出相反結果的神諭設定,並追蹤對角化構造必須保護哪些查詢。

第 5 章 · 3 節

計數與電路

見證計數與多項式大小非一致電路。

定理 9 · 定義 1反例 3視角 1證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    見證計數與非一致電路

    研究 #P 見證計數及非一致電路族。

  2. 5.2

    多數接受與計數

    以精確多數定義 PP,將其與見證計數相聯繫,並證明基本的包含關係及補集封閉性。

  3. 5.3

    保計數歸約與積和式

    透過布爾閘保持見證計數,解釋積和式,並計算其奇偶性。

第 6 章 · 1 節

概率界

Bernoulli 指數尾界的推導。

定理 3 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    Bernoulli 試驗的指數尾界

    推導 Bernoulli 指示變量集中界及多數表決放大。

第 7 章 · 1 節

隨機計算與建議字串

重溫隨機算法的錯誤放大,並以聯集界證明固定隨機帶的非一致性結論。

定理 3 · 定義 2反例 2視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    錯誤放大與固定隨機性

    重溫隨機算法的錯誤放大,並以聯集界證明固定隨機帶的非一致性結論。

第 8 章 · 4 節

交替與多項式層級

交替與多項式層級

定理 11 · 定義 4反例 4視角 3證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    交替與多項式層級

    建立帶量詞的驗證者類別,並觀察補集與嵌套如何改變量詞。

  2. 8.2

    層級各層上的完全量化公式

    把多項式時間謂詞編碼為公式,而不增加一次量詞交替。

  3. 8.3

    小電路與多項式層級

    利用非一致見證搜尋及明確的量詞,證明 Karp–Lipton 塌縮定理。

  4. 8.4

    電路建議與層級坍縮

    聯繫非一致建議與電路、計數小電路,並證明一個有條件的層級坍縮。

第 9 章 · 4 節

互動證明

互動證明

定理 13 · 定義 6反例 2視角 2證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    互動證明與圖非同構

    定義互動證明中的完備性與可靠性,並分析圖非同構協議。

  2. 9.2

    求和檢驗協議

    透過互動式低次數檢驗與適應性可靠性證明,驗證有限域上所聲稱的求和值。

  3. 9.3

    從多項式空間到互動式證明

    運用多重線性矩陣延拓與求和檢驗,證明 PSPACE 包含於 IP。

  4. 9.4

    Merlin、Arthur 與公開隨機性

    以明確的量詞定義 MA 與 AM,並證明 MA 包含於 AM。

第 10 章 · 1 節

機率可檢驗證明

機率可檢驗證明

定理 4 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 10.1

    概率可驗證證明與間隙歸約

    定義隨機存取證明驗證,並由一個所述的間隙定理推導出有條件的近似障礙。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情