CS40012/174006 Theory of computation, Spring 2003

Recap
Alphabets, strings, languages, finite representation of languages, Turing machines, R.E. and recursive languages, Church-Turing thesis.
Computability theory
Decidable and undecidable languages, the diagonalization and universal languages, the halting problem, undecidable problems about Turing machines, Rice's theorem, Post correspondence problem.
Complexity theory
- Time complexity: Complexity classes P, NP, co-NP, NP-complete and NP-hard, polynomial-time reductions, Cook-Levin theorem, some NP-complete problems.
- Space complexity: Complexity classes PS, NPS, PS-complete and PS-hard, log-space computations, complexity classes L, NL and NL-complete.
- Hierarchy theorems: Time and space hierarchy, complexity class EXPSPACE.
- Randomized and probabilistic algorithms: Randomized Turing machines, complexity classes RP and ZPP.
- Parallel algorithms: Boolean circuits, complexity classes NC and P-complete.
- Alternating Turing machines: Alternating time and space, complexity classes AP, APSPACE and AL.
- Cryptography: One-way and trapdoor functions, secret-key and public-key cryptography.
If time permits, I will talk about additional assorted topics to be decided later.

[HMU]	John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, second edition, Pearson Education, Singapore.
[Sipser]	Michael Sipser, Introduction to the theory of computation, Thomson Asia Pte Ltd, Singapore.
[Papa]	Christos H. Papadimitriou, Computational complexity, Addison Wesley.

I will mostly follow [HMU] and [Sipser]. The last reference [Papa] is a bit advanced and more suitable for graduate courses.

Test	Time	Total points	Duration	Syllabus	Question paper
Class test I	January end / February beginning	10	30 min+	To be decided later	Not yet available
Mid-semester exam		30	1 hr+	To be decided later	Not yet available
Class test II	March end / April beginning	10	30 min+	To be decided later	Not yet available
End-semester exam		50	3 hr+	To be decided later	Not yet available

(Unless otherwise stated, all tests are open-note and open-time.)