Computational Complexity 计算复杂性

Presentation on theme: "Computational Complexity 计算复杂性"— Presentation transcript:

1 Computational Complexity 计算复杂性
姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502

2 教材 作业 成绩 作业 *40% + 期末考试*60% (暂定)
每章结束后有4~5道题目. 每道题要有完整的完整的解题过程，中英文不限。 作业 *40% + 期末考试*60% (暂定) 成绩

3 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?

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

5 Turing machines

6 Example （Palindrome）

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

8 Time complexity and time-constructible functions

9 Robustness of our definition

10 Oblivious Turing machines

11 Indexing TM and universal TM

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

13