Computational complexity

C.-H. L. Ong

Sixteen-hour lecture course. Final-year computer science undergraduate

Aim

This course gives an introduction to the key ideas and techniques in computational complexity.

Syllabus

Reducibility among computational problems. Randomized problems. Polynomial time combinatorial problems. NP-completeness. Simple polynomial transformations. Pseudo-polynomial time algorithms. Approximation algorithms. Complexity classes beyong NP. Undecidability. The halting problem.

Synopsis

• Turing machine and elements of computability. Multitape deterministic Turing machine. Church-Turing Thesis. Decision problem. Undecidability. Halting problem. Recursive enumerability. m-reducibility.
• Polynomial time. Deterministic time complexity class. Time-constructiblity. Linear Speed-up Theorem. P. EXP Polynomial reducibility. Polytime algorithms: 2-satisfiability, 2-colourability. Diagonalization.
• NP and NP-completeness. Non-deterministic Turing machine. NP Polynomial-time verification. NP-completeness. Cook-Levin Theorem. Polynomial transformations: 3-satisfiability, clique, colourability, Hamilton cycle, partition problems. Pseudo-polynomial time. Strong NP-completeness. 3-partition. Knapsack. Oracle Turing machine. Turing reducibility. NP-hardness.
• Space complexity. Deterministic space complexity class. Space-constructibility. Linear Space Compression Theorem. PSPACE, NPSPACE, PSPACE = NPSPACE. PSPACE-completeness.
• Optimization and approximation. Combinatorial optimization problems. Relative error. Bin-packing problem. First-fit algorithm. Polynomial and fully polynomial approximation schemes. Vertex cover, travelling salesman problem, minimum partition.
• Primality testing and randomized algorithms. Pratt's theorem. Rabin's theorem. Monte-Carlo vs Las Vegas algorithms. Probabilistic complexity classes: RP, ZPP, PP, BP.

Reading list

[1] D. P. Bovet and P. Crescenzi. Introduction to the Theory of Complexity. Prentice International Series in Computer Science. Prentice Hall, 1994.

[2] J. L. Balcazar, J. Diaz, and J. Gabarro. Structural Complexity I. Springer-Verlag, 1995.

[3] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990.

[4] M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the Theory of NP-Completeness. Freeman, 1979.

[5] D. Harel. Algorithmcs: The Spirit of Computing. Addison-Wesley, 2nd edition, 1992.

[6] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[7] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[8] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[9] M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, January 1997.

Course material

Handouts

• Section 1: Introduction - Turing machines
• Section 2: Church-Turing thesis and undecidability
• Section 3: Time complexity and the class P
• Section 4: The class NP and NP-completeness
• Section 5: Basic structure, Turing reducibility and NP-hardness
• Section 6: Space complexity
• Section 7: Optimization Problems and their Approximability
• Section 8: Primality Testing and Randomized Algorithms

Hardcopies of the above are available from the Reception. Here is a list of Additions, Corrections and Typos. [Last updated on 4 March 1999] A revised version (28 Map 1999) of this year's notes is available.

The above documents are in PostScript which can be read using ftp-able software such as Acrobat Reader produced by Adobe.

[Last updated on 4 March 1999 by Luke Ong]