Time: 9:10--12:00 Wednesday
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
- References
- Teaching Assistants
- 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.
|
Examinations and grading
-
There was a mid-term exam on November 10, 2004 (closed book).
- The examination will cover the lecture notes up to p. 251 given on
October 20, 2004
(roughly Chapters 1 through 8 of the textbook, excluding Chapters 5 and 6).
- The use of electromagnetic devices to transmit or receive signals during
the examination will guarantee eviction from the class.
- Bring your student photo ID for possible spot checks.
- Students with an odd-numbered student ID take the test during
9:20--10:30. You shall not leave the room before 10:40.
- Students with an even-numbered student ID take the test during
10:50--12:00.
-
Answers (prepared by the TA)
-
There will be a final exam on January 12, 2005 (closed book).
- The examination will cover the lecture notes from p. 251
(October 20, 2004) up to p. 559.
- The use of electromagnetic devices to transmit or receive signals during
the examination will guarantee eviction from the class.
- Bring your student photo ID for possible spot checks.
- Students with an even-numbered student ID take the test during
9:20--10:30. You shall not leave the room before 10:40.
- Students with an odd-numbered student ID take the test during
10:50--12:00.
-
Answers (prepared by the TA)
-
Your grades will be based on the grades of the exams.
The major results covered in the course, time permitting, are listed below
for your reference.
Complexity measures
(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
Applications to security ....
Distributed systems
Computational learning theory,
complexity of neural
networks, and the
VC dimension (Valiant 1984,
A. Blum 1989, Blumer, Ehrenfeucht,
Haussler & Warmuth 1987).