課程內(nèi)容：

本課程是對計算復雜性理論的獨立介紹。除了對基本算法和數(shù)學符號有所了解之外，無需其他先決條件。教學將完全采用傳統(tǒng)授課方式，輔以規(guī)定的課程教材。課程旨在使學生熟悉計算復雜性理論的基本概念和技術。

課程大綱：

- 有向圖：拓撲排序和塔讓算法。

- 無向圖：并集查找、Grzegorczyk層次、并集查找的復雜度。

- 流網(wǎng)絡：最優(yōu)流、二維匹配、最小成本最大流。

- 圖靈機和可計算性。

- 計算復雜度的度量。

- 分離定理。

- 命題邏輯和復雜度：SAT、k-SAT、Horn-SAT和QBF-SAT（第一部分）。

- 困難和簡化：庫克定理。

- 圖論問題：三色問題、哈密頓電路和歐拉電路、TSP。

- 薩維奇定理和伊默曼-塞萊普塞尼定理。

- 命題邏輯與復雜性：SAT、k-SAT、Horn-SAT和QBF-SAT（第二部分）。

- 拉德納定理。

- 其他內(nèi)容：一階邏輯與復雜性：決策問題。

學習成果：

通過本課程的學習，學生將能夠：

1、理解與圖靈計算模型相關的常見復雜度類別的標準層級。

2、理解（問題）簡化與計算難度的概念，并熟悉確定較低復雜度界限的技術——特別是NPTime-hardness。

3、熟悉復雜度理論中最重要、最核心的定理（庫克定理、拉德納定理、薩維奇定理、伊莫曼-塞萊普塞尼定理）。

4、查閱并理解復雜度理論方面的科學文獻。

5、分析一系列問題的計算復雜度。