計算復雜性課程

• Chapter 1 時間復雜性
• Chapter 2 空間復雜性
• Chapter 3 NP完全和多項式譜系
• Chapter 4 電路

Chapter 1 時間復雜性

• 圖靈機
• 時間可構造性（不等價）
• 通用圖靈機對數時間放大（$T\to cTlogT$）
• 對角線方法
• 丘奇-圖靈論題（可計算函數就是圖靈機可計算函數，“遞歸定理”）
• 加速定理
  • blum加速定理
  • 時間壓縮定理/線性加速：$?T(n)+n+2$
• 時間復雜性類（$P,EXP$）
• 間隙定理（TIME$(b(x))=$TIME$(r(b(x)))$）
• 非確定圖靈機
  • $P?NP?EXP?NEXP$
  • 通用非確定圖靈機$T\to T$，缺點是不一定終止
• 命題邏輯
  • 字(變量或變量否)，單項式(若干字的合取)，語句(若干字的析取)，析取范式(若干單項式的析取)，合取范式(若干語句的合取)
  • 永真式：所有可滿足的合取范式的集合
  • SAT$\in$NP
• 謂詞邏輯
  • QBF：所有為真的量化布爾公式的集合
• 計算的邏輯刻畫（格局圖鄰接矩陣表示）
• 時間譜系定理
  • $f(n)\log f(n)=o(g(n))$，則TIME$(f(n))?$ TIME$(g(n))$
  • 非確定時間譜系定理：$f(n+1)=o(g(n))$，則NTIME$(f(n))?$ NTIME$(g(n))$
• 概率圖靈機
• 神諭圖靈機
• 歸約
  • Karp歸約：多項式時間可計算的$m$-歸約函數，則稱$A$可卡普規約到$B$，記作$A{\le }_{K}B$
  • Cook歸約：$A\in$ P${}^B$，則稱$A$可庫克規約到$B$，記作$A{\le }_{C}B$

Chapter 2 空間復雜性

• 緒論
  • 空間壓縮定理：$S(n)\to ?S(n)+1$
  • 空間可構造性（等價）
  • 通用圖靈機線性空間放大（$S\to cS$）
  • 空間譜系定理：$f(n)=o(g(n))$，則SPACE$(f(n))?$ SPACE$(g(n))$
  • 格局圖：鄰接矩陣表示，每一步是${?}_{M,x}(C,C^{\prime })$
    • ${?}_{M,x}(C,C^{\prime })$賦值：對數空間$O(\log S)$，多項式時間$O(|{?}_{M,x}(C,C^{\prime })|)=O(S\log S)$
    • ${?}_{M,x}(C,C^{\prime })$求值：常數空間，多項式時間$O(S\log S)$
• 對數空間類（$L,NL$）
  • 對數空間歸約：若存在隱式對數空間可計算的從$A$到$B$的歸約，則$A{\le }_{L}B$
  • 可達性問題$\in$ NL-完全
• 多項式空間類（PSPACE,NPSPACE）
  • TQBF$\in$ PSPACE-完全
  • 薩維奇定理：NSPACE($S$)$?$ SPACE($S^2$)
• 伊默爾曼-斯澤勒普森伊定理
  • 薩維奇定理$\to$ coNPSPACE=NPSPACE
  • 可達性問題$\in \overline{NL}\to coNL=NL$
  • 可達性問題${\le }_L$ 2SAT$\to$ 2SAT$\in$NL-完全
• 霍普克羅夫特-保羅-瓦里昂特定理：TIME$(S(n))?$ SPACE$(S(n)/logS(n))$

Chapter 3 NP完全和多項式譜系

• NP完全性
  • 若$?A\in$NP，均有$A{\le }_{K}B$，則$B$是NP-難的；若$B$是NP-難的且$B\in$ NP，則$B$是NP-完全的。
• Cook-levin定理：SAT$\in$ NP-完全
• Ladner定理：若P$=$NP，則P$\cup$NPC$=$ NP
• 貝克-吉爾-索羅維定理：存在$A,B$使得P${}^A$=NP${}^A$且P${}^B=$ NP${}^B$
• 多項式譜系：NP$?$ NP${}^{NP}?$ NP${}^{N{P}^{NP}}?\dots \dots$
• 譜系的邏輯刻畫
• 譜系的交替機刻畫
• 無限譜系假設：$?i,$PH${}_i?$ PH${}_{i+1}$

Chapter 4 電路

• 電路譜系定理
  • shannon定理：絕大多數$n$-元布爾函數的電路復雜性大于$\frac{2^n}{n}?o(\frac{2^n}{n})$
  • 最難的$n$-元布爾函數的電路復雜性有上界$\frac{2^n}{n}+o(\frac{2^n}{n})$
  • 存在$c<1$，對足夠大的$n$，最難的$n$-元布爾函數的電路復雜性有下界$\frac{2^n}{n}(1+c\frac{\log n}{n})$
  • 最難的$n$-元布爾函數$f$的電路復雜性$|C_f|$滿足下列不等式：$\frac{2^n}{n}(1+\frac{\log n}{n}?O(\frac{1}{n})\le |C_f|\le \frac{2^n}{n}(1+3\frac{\log n}{n}+O(\frac{1}{n}))$
  • 電路譜系定理：若有$?>0$滿足$n<(2+?)S(n)<S^{\prime }(n)<<2^n/n$，則有SIZE$(S(n))?$ SIZE$(S^{\prime }(n))$
• uniform circuit：限制多項式大小電路族的能力，使它們和多項式時間圖靈機的計算能力一樣。只考慮多項式時間可判定問題
  • 一個語言可被一致電路族接受當僅當該語言在$P$中
  • 對所有$L\in NP$，有$L{\le }_{L}CKT?SAT$
  • $CKT?SAT{\le }_{L}SAT$
• $P/poly$：讓多項式時間圖靈機擁有額外的信息，使它們和多項式大小的電路族的能力一樣，給它們一些建議。
  • $P/poly={\cup }_{c,c^{\prime }}$SIZE$(c{n}^{c^{\prime }})$
  • $P?P/poly$
  • 若$NP?P/poly$，則$PH=P{H}_2$
  • 若$EXP?P/poly$，則${\sum }_{2}SAT$是$EXP$-難的
• 并行計算
  • NC
    • $N{C}^d$：語言$L$在$N{C}^d$中當僅當$L$可由一個高度函數為$O({\log }^d(n))$的一致電路族所接受
    • 高效并行計算類$NC$定義為${\cup }_{d\in N}N{C}^d$
  • 圖的可達性問題在$N{C}^2$中
  • AC：交替電路
    • NC：與門和或門的扇入=2，AC：與門和或門的扇入$\ge$ 2
    • $AC={\cup }_{d\in N}A{C}^d$
    • $N{C}^i?A{C}^i?N{C}^{i+1}$
    • $AC=NC$
• P-完全性
  • 隱式對數空間可計算函數具有高效并行算法
  • 若$L\in P$-完全的，$L\in NC$當僅當$NC=P$

總結

以上是生活随笔為你收集整理的计算复杂性课程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。