課程名稱:

先修課程:

課程目標:

參考書:

1. Theory of Computational Complexity, Ding-Zhu Du and Ker-I Ko.
2. Computational Complexity, Papadimitiou.
3. Introduction to the Theory of Computation, Michael Sipser

課程內容:

What makes some problems computationally hard and others easy?

We don't know the answer to the above, though it has been intensively researched for the past 25 years. So far one of the important achievements of complexity theory is researchers have found an elegant scheme for classifying problems according to their computational difficulty. One applied area that has been affected directly by complexity theory is the ancient field of cryptography. Complexity theory has pointed cryptographers in the direction of computationally hard problems around which they have designed revolutionary new code.

課程綱要:

1. Time Complexity
2. Space Complexity
3. Hierarchy Theorem
4. Circuit Complexity
5. Polynomial hierarchy
6. Randomized Computation
7. Counting class
8. Interactive Proof system
9. Advanced Topics in Complexity Theory