Fall 2026 · CUHK-Shenzhen · 3 units
CSC 6011: Theory of Computation
Course overview
What are the fundamental capabilities and limitations of computers? This course introduces the foundations of computability and computational complexity, and how to classify computational problems by the resources needed to solve them.
We begin with automata and formal languages, then study Turing machines, decidability, and reductions. Complexity topics include P versus NP, NP-completeness, time and space complexity, randomized computation, interactive proofs, and hardness of approximation. The course also covers communication complexity and connections between Transformers and EXPSPACE-completeness.
Prerequisites: No formal prerequisites. Students should be comfortable with mathematical reasoning, proofs, and basic discrete mathematics.
Class information
- Lectures: Monday and Wednesday, 4:00–5:20 PM, Teaching A, Room 107.
- Instructor: Tao Lin (林涛), lintao@cuhk.edu.cn.
- Teaching assistant: Xingyu Wang (王星宇), 225040497@link.cuhk.edu.cn.
- Instructor office hour (tentative): Thursday, 5:00–6:00 PM, Daoyuan Building (道远楼), Room 420c.
- TA office hours (tentative): Wednesday, 7:00–9:00 PM, Zhixin Building (知新楼), Room 247.
Syllabus and slides
The indicative teaching plan below follows the course syllabus (version 2, September 7, 2026). The schedule is subject to adjustment. Further slides will be added as they become available.
| Week | Topics | Slides |
|---|---|---|
| 1 | Introduction. Finite automata (DFA and NFA). Regular languages. | Lecture 1 (PDF) |
| 2 | Nonregular languages, pumping lemma. | Not yet posted |
| 3 | Context-free languages, pushdown automata. | Not yet posted |
| 4 | Turing machines, the Church–Turing thesis. | Not yet posted |
| 5 | Decidability, diagonalization. | Not yet posted |
| 6 | Reduction. Time complexity. | Not yet posted |
| 7 | P and NP, NP-completeness. | Not yet posted |
| 8 | Cook–Levin theorem. Midterm exam. | Not yet posted |
| 9 | Space complexity, PSPACE, L, NL, Savitch’s theorem. | Not yet posted |
| 10 | [ICLR’26 paper]: Transformers & EXPSPACE-completeness. | Not yet posted |
| 11 | Randomized computation, RP, BPP. | Not yet posted |
| 12 | Interactive proofs, IP = PSPACE. | Not yet posted |
| 13 | Approximation algorithms, hardness of approximation, PCP theorem. | Not yet posted |
| 14 | Communication complexity. | Not yet posted |
Learning outcomes
By the end of the course, students will be able to:
- Formalize problems using standard models of computation, analyze their capabilities and limitations, and prove results about decidability, reducibility, and complexity.
- Classify problems into major complexity classes and construct rigorous reductions and impossibility arguments.
- Apply theoretical computer science concepts to the analysis of algorithms and data science problems.
Assessment
| Component | Weight |
|---|---|
| Homework | 30% |
| Midterm exam | 30% |
| Final exam | 40% |
Exams: The midterm and final are open-book. Text materials are allowed; digital devices and AI tools are not. Students must complete exams independently.
Homework and AI: AI tools may be used, but students must write their own solutions and explain how they used AI. Direct submission of AI output is not allowed.
Reading
There is no required textbook. Recommended references are:
- Michael Sipser, Introduction to the Theory of Computation, 3rd edition. Cengage Learning.
- John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation. Pearson.
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. Cambridge University Press.
- Eyal Kushilevitz and Noam Nisan, Communication Complexity. Cambridge University Press.