Computing Theory Course

Computing Theory

Time: 9:10--12:20 Tuesday

If IP=PSPACE, then TCP=NP.
---Class of 2000, M.S. (overheard)

A professor always included this question on his final exams:
"What did you think of this course?"
He discontinued the practice after receiving this response:
"This was the most complete course I ever took.
Anything we didn't go over during class
was covered in the final exam."
---Adapted from Reader's Digest

Two hunters are being pursued by a bear;
one stops to change into his running shoes.
The other tells him he is crazy: there is no
way he can run faster than a bear.
``I don't have to run faster than a bear,''
replies the first. ``I only have to run faster than you.''
The Economist, 18 March 2002

Textbooks
- C. H. Papadimitriou, Computational Complexity. Addison-Wesley, 1995. Errata for the 1994 edition.
References
- M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
- J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, 1981.
Teaching Assistants
- 陸裕豪 Lok, U Hou
- 蔡芸琤 Tsai, Yun-Cheng (Pecu)
- 文國煒 Wen, Kuo-Wei (Jimmy)
- 吳承憲 Wu, Cheng-Hsien
- TA Hours
  - 15:00-17:00 on Thursdays in room 446（陸裕豪、文國煒）
  - 10:00-12:00 on Fridays in room 446（蔡芸琤、吳承憲）
- CEIBA system
Internet Resources

To the students,

This course emphasizes computational complexity and its applications. We will go over, in my opinion, the most interesting and/or important results in the field. You are expected to read the textbook for any background knowledge not covered in the lectures if your undergraduate education has not prepared you for this course. The textbook will, in general, be followed.

The mathematical techniques used in this course are wide-ranging but accessible. Undergraduate discrete mathematics course should be more than adequate. Math majors should be prepared to find standard mathematics used in unexpected ways. Combinatorics, probability, graph theory, number theory, and, to a less extent, group theory are the principal analytical tools. We shall skip predicate logic (Frege 1879) and the associated profound results of completeness and incompleteness (Godel 1930, 1931).

I hope you will be rewarded with the insights, sense of beauty, and applications that some of the results convey. There is also the satisfaction that, unlike many other fields in computer science (including those taught by me), many of the topics will still be taught to students decades from now.

Homework should be turned in on time, before 9:10. Otherwise, it will be considered late. If you have to use emails to turn in the homework, please use the PDF format with your student ID number as the file name and send it using your NTU or NTUCSIE email account. The time stemp will be used to determine if the homework is late or not. You are expected to finish your own homework on your own. Do not copy or collaborate with fellow students. Never give your homework to other students or publish your homework because it may be copied and you in turn may be suspected of copying other's homework!

Notes [ 2001, 2002, 2003, 2004, 2005, 2006, 2008a, 2008b, 2009, 2010, 2011 ]

2011.09.13
2011.09.20
2011.09.27
2011.10.04 & 1st homework due & solutions
2011.10.11
2011.10.18
2011.10.25 & 2nd homework due & solutions
2011.11.01
2011.11.08 & mid-term exam & solutions
2011.11.15 Holiday
2011.11.22 & 3rd homework due & solutions
2011.11.29
2011.12.06
2011.12.13 & 4th homework due & solutions
2011.12.20
2011.12.27
2012.01.03 & 5th homework due & solutions
2012.01.10 & final exam & solutions

Examinations and grading

There is a mid-term exam on November 8, 2011 (closed book).
- Locations: Rooms 101, 111 and 103 of the CSIE building.
- To avoid congestion, you should take the test in the room based on your student ID as follows:
  - R103 for R00922xxx with odd numbers and Dxxxxxxxx.
  - R101 for R00922xxx with even numbers.
  - R111 for the rest of the students.
- The examination will cover the lecture notes up to November 1, 2011, plus the corresponding materials in the textbook.
- The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the classroom.
- Please bring your student photo ID for possible spot checks.
There is a final exam on January 10, 2012 (closed book).
- Locations: Rooms 101, 111 and 103 of the CSIE building.
- To avoid congestion, you should take the test in the room based on your student ID as follows:
  - R103 for R00922xxx with odd numbers and Dxxxxxxxx.
  - R101 for R00922xxx with even numbers.
  - R111 for the rest of the students.
- The examination will cover the lecture notes from November 15, 2011, up to January 3, 2012, plus the corresponding materials in the textbook.
- The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the classroom.
- Please bring your student photo ID for possible spot checks.

The major results covered in the course, time permitting, are listed below for your reference.

Computation models and computability

Turing machines (Kleene, Turing, Church, Post 1935-1936).
Oracle Turing machines (Turing 1939, Baker, Gill & Solovay 1973).

Complexity measures

Time & space (Hartmanis & Stearns 1965, Rabin 1960).
Program size (Kolmogorov complexity) (Solomonoff 1964, Kolmogorov 1965, Chaitin 1966).
Circuit complexity and exponential bounds (Boole 1847, Shannon 1938, Quine, Ljapunov 1958, Razborov 1985, Furst, Saxe & Sipser 1984, Yao 1985, Hastad 1988).
Feasible computation: P & NP classes (Edmonds 1965, Cook 1971, Karp 1972).

Complexity classes

P, NP, co-NP, NP-complete (Cook 1971, Karp 1972, Levin 1973).
PSPACE and PSPACE-complete (Karp 1973).
P-complete (Ladner 1975).
#P (Valiant 1979).
IP (Goldwasser, Micali & Rackoff 1985).
PCP (Arora, Lund, Motwani, Sudan & Szegedy 1992).
Randomized complexity classes: R, ZPP, BPP, PP (Gill 1976).
L, NL, parallel complexity classes (Pippenger 1979).
Polynomial hierarchy (Karp 1972, Meyer & Stockmeyer 1973).

Tackling complexity

Randomized algorithms (Rabin 1976, Solovay & Strassen 1977, Miller 1976).
Probabilistic methods (Szele 1943, Erdos 1947).
Approximation & approximability (Johnson 1974, Arora, Lund, Motwani, Sudan & Szegedy 1992).
On-line algorithms and competitive analysis (Yao 1980, Sleator & Tarjan 1985).

Applications to security ....

Public-key cryptography & RSA (Diffie & Hellman 1976, Merkle 1978, Rivest, Shamir & Adleman 1978).
Cryptography-based random number generation (Shamir 1981, Yao 1982, Blum & Micali 1984).
Interactive proof systems (Goldwasser, Micali & Rackoff 1985).
Watermarking (Cox, Kilian, Leighton & Shamoon 1996).
Primality testing in P (Agrawal, Kayal & Saxena 2002).

Distributed systems

Communication complexity (Yao 1982).
Impossibility & complexity to reach consensus in distributed systems (Lamport, Shostak & Pease 1980, Fischer, Lynch & Paterson 1985).

Computational learning theory, complexity of neural networks, and the VC dimension (Valiant 1984, A. Blum 1989, Blumer, Ehrenfeucht, Haussler & Warmuth 1987).