Complexity Theory (복잡도 이론)

Class Info

Class Number: APPM 814
Dates: Mar 6, 2012 - Jun 7, 2012
Room: NS 319
Meeting time:
Tuesday 16:30 - 17:45
Thursday 16:30 - 17:45

Purpose: Introduction to Mathematical Complexity Theory and Computation
Text:
Peter Gacs and Laszlo Lovasz, Computation Complexity, Lecture Notes
Links
Homework

Syllabus

Week Topics Chapters
1 The Turing Machine 1 & 2
2 RAM and Logic Circuits 2
3 Decidability 2 & 3
4 Undecidable Problems 3
5 Complexity Classes 4
6 Space and Time 4
7 Non-Deterministic Computation 5
8 Midterm Exam
9 NP-Completeness 5
10 Randomization 6
11 Information Complexity 7
12 Kolmogorov Complexity 7
13 Parallel Computing 8
14 Decision Trees 9
15 Final Exam

Grading

We will have a mid-term test in April and a final exam in June .
The grades will be accorded the following weights.
Attendance 10%
Mid-term: 40%
Final: 50%

Homework

According to agreement.
Last modified: Tue Mar 13 16:22:30 KST 2012