Computational Complexity 计算复杂性 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502

教材 作业 成绩 作业 *40% + 期末考试*60% (暂定) 每章结束后有4~5道题目. 在第二次上课前发送到助教（刘明谋）邮箱liu.mingmou@smail.nju.edu.cn 每道题要有完整的完整的解题过程，中英文不限。 作业 *40% + 期末考试*60% (暂定) 成绩

Computational complexity theory From Wikipedia Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating the resulting complexity classes to each other. What is computation? How to measure the computational difficulty?

History Equivalent! Calculus Newton-Leibniz 1687 What is infinitesimal? 1817: Epsilon-delta definition Cauchy, Bolzano 1817 Rigorous def. of infinitesimal Set theory Cantor 1880s What is infinite Russell paradox (what is a set?) Russell 1901 ZFC axioms Zermelo–Fraenkel 1922 Hilbert program Hilbert 1920s Soundness/consistency Completeness Gödel’s incompleteness theorems Gödel 1931 Gödel’s first incompleteness theorem Gödel’s second incompleteness theorem What is computation? Recursive functions Gödel 1931 Turing machines Turing 1936 Lambda calculus Church 1930s …… Equivalent!

Turing machines

Example （Palindrome）

What is computation? Church-Turing Thesis Every physically realizable computation can be simulated by a Turing machine.

Time complexity and time-constructible functions

Robustness of our definition

Oblivious Turing machines

Indexing TM and universal TM

Strong Church-Turing Thesis Every physically realizable computation can be simulated by a Turing machine with polynomial overhead. Challenge： Quantum Computers