This course is set for junior graduate students, who are expected to have good understandings of mathematics and knowledge in basic theoretical computer science.

The course introduces main contents of computational theory with an emphasis on important topics concerning modern and contemporary complexity theories, which enables students to know major issues and results in the field of complexity theories. It also helps students to determine their future research interests through understandings of algorithm.

Topics covered in the course are: review of main contents of computability theory, introduction of basic themes of complexity theory, including basic complexity classes like P, NP, PSPACE and BPP; proof of the non-existence of circuit and Parity in AC0; Hierarchy Theorems of time and space; main results of derandomization; PCP theorem and non-approximatability; theoretical coding; and etc.

The course is mainly conducted through lectures and series seminars, supplemented by featured discussions. The students are required to take thesis reading exercises and give summary reports, with a view to helping them find their future research interests.