你的進度
0/ 33 節已標記完成
下一節: 隨機化計算與放大
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI3360 筆記裏的內容
數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 94 · 定義 50 · 反例 33 · 概念視角 17 · 思想史 1 · 證明透視 33
第 1 章 · 4 節
隨機化複雜度
公平隨機位元、RP、BPP、放大、零錯誤計算與恆等測試
- 1.1
隨機化計算與放大
定義單側錯誤與雙側錯誤,並利用獨立重複證明多數放大。
- 1.2
零錯誤隨機計算
以有界截斷及獨立單側算法證明零錯誤類別的刻畫。
- 1.3
方差界與隨機恆等檢驗
證明方差放大界,並分析使用公平位元的多項式恆等測試。
- 1.4
仿射雜湊與有限獨立性
證明質數域上的兩兩獨立性,並區分雜湊值獨立與碰撞事件獨立。
第 2 章 · 4 節
非確定性與歸約
NP 與 coNP 證明、多項式歸約,以及 3-SAT 到 CLIQUE 的證明。
- 2.1
非確定性、歸約與完全性
區分 NP 與 coNP 證明並證明圖歸約,以 3-SAT 困難性為背景。
- 2.2
把驗證者轉化為可滿足性實例
為有界計算構造布爾電路,並證明電路可滿足性是 NP 完全的。
- 2.3
閘約束、SAT 與三文字子句
用輔助變量保持電路的共享結構,並通過證明兩個方向與規模界來證明可滿足性歸約。
- 2.4
見證搜尋、判定與類 DP
由判定查詢中復原多項式長度的見證,並謹慎地結合 NP 與 coNP 條件。
第 3 章 · 7 節
空間與可達性
空間模型、有向可達性與組態計數。
- 3.1
空間與有向可達性
定義對數空間計算,證明有向可達性屬於 NL 及 NL 包含於 P。
- 3.2
Savitch 定理:模擬非確定性空間
透過隱式組態圖證明一般的平方空間模擬,解釋多項式空間類相等及歸約的複合。
- 3.3
量化布爾公式、空間與互動證明
證明 TQBF 為 PSPACE 完全,並證明互動證明具有多項式空間上界。
- 3.4
可達性的完全性與中點遞歸
構造組態圖歸約並分析確定性的中點遞歸。
- 3.5
為甚麼非確定性對數空間在補運算下封閉
利用歸納計數在對數空間內驗證不可達性。
- 3.6
2-SAT、蘊含圖與 NL 完全性
證明蘊含圖判據,並用對數空間可達性刻畫二文字可滿足性。
- 3.7
確定性空間層級
利用組態數目界限與有界模擬,證明更多的空間可判定嚴格更多的語言。
第 4 章 · 4 節
計算與模型
判定問題、資源界限、編碼與不可判定性。
- 4.1
計算、資源與對角化
定義計算資源,並用計數與對角化研究可判定性。
- 4.2
用一條紙帶模擬多條紙帶
區分舊、新讀寫頭標記,證明固定紙帶數的多項式時間穩健性。
- 4.3
確定性時間層級定理
利用帶時鐘的通用模擬與對角化方法,分離確定性時間界。
- 4.4
神諭世界與相對化的局限
構造使 P 與 NP 問題得出相反結果的神諭設定,並追蹤對角化構造必須保護哪些查詢。
第 5 章 · 3 節
計數與電路
見證計數與多項式大小非一致電路。
- 5.1
見證計數與非一致電路
研究 #P 見證計數及非一致電路族。
- 5.2
多數接受與計數
以精確多數定義 PP,將其與見證計數相聯繫,並證明基本的包含關係及補集封閉性。
- 5.3
保計數歸約與積和式
透過布爾閘保持見證計數,解釋積和式,並計算其奇偶性。
第 6 章 · 1 節
概率界
Bernoulli 指數尾界的推導。
- 6.1
Bernoulli 試驗的指數尾界
推導 Bernoulli 指示變量集中界及多數表決放大。
第 7 章 · 1 節
隨機計算與建議字串
重溫隨機算法的錯誤放大,並以聯集界證明固定隨機帶的非一致性結論。
- 7.1
錯誤放大與固定隨機性
重溫隨機算法的錯誤放大,並以聯集界證明固定隨機帶的非一致性結論。
第 8 章 · 4 節
交替與多項式層級
交替與多項式層級
- 8.1
交替與多項式層級
建立帶量詞的驗證者類別,並觀察補集與嵌套如何改變量詞。
- 8.2
層級各層上的完全量化公式
把多項式時間謂詞編碼為公式,而不增加一次量詞交替。
- 8.3
小電路與多項式層級
利用非一致見證搜尋及明確的量詞,證明 Karp–Lipton 塌縮定理。
- 8.4
電路建議與層級坍縮
聯繫非一致建議與電路、計數小電路,並證明一個有條件的層級坍縮。
第 9 章 · 4 節
互動證明
互動證明
- 9.1
互動證明與圖非同構
定義互動證明中的完備性與可靠性,並分析圖非同構協議。
- 9.2
求和檢驗協議
透過互動式低次數檢驗與適應性可靠性證明,驗證有限域上所聲稱的求和值。
- 9.3
從多項式空間到互動式證明
運用多重線性矩陣延拓與求和檢驗,證明 PSPACE 包含於 IP。
- 9.4
Merlin、Arthur 與公開隨機性
以明確的量詞定義 MA 與 AM,並證明 MA 包含於 AM。
第 10 章 · 1 節
機率可檢驗證明
機率可檢驗證明
- 10.1
概率可驗證證明與間隙歸約
定義隨機存取證明驗證,並由一個所述的間隙定理推導出有條件的近似障礙。