Time: 2:10--5:00 Wednesday and Thursday
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.
|
-
2006.09.20 & 2006.09.21
-
2006.09.27
&
2006.09.28
-
2006.10.04
&
2006.10.05
-
2006.10.11
&
2006.10.12
-
2006.10.18
&
2006.10.19
-
2006.10.25
&
2006.10.26
-
2006.11.01
&
2006.11.02
-
2006.11.08
&
2006.11.09
-
2006.11.15 (university holiday)
&
2006.11.16
-
2006.11.22
&
2006.11.23 (mid-term exams)
-
2006.11.29
&
2006.11.30
-
2006.12.06
&
2006.12.07
-
2006.12.13
&
2006.12.14
-
2006.12.20
&
2006.12.21
-
2006.12.27
&
2006.12.28
-
2007.01.03
&
2007.01.04
-
2007.01.10
&
2007.01.11
-
2007.01.17
&
2007.01.18 (final exams)
Examinations and grading
-
There was a mid-term exam on November 22, 2006 (closed book).
- The examination will cover the lecture notes up to p. 335 given on
November 1, 2006
(roughly Chapters 1 through 9 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.
-
There was a mid-term exam on November 23, 2006 (closed book).
- The examination will cover the lecture notes up to p. 335 given on
November 2, 2006
(roughly Chapters 1 through xxx 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.
-
There will be a final exam on January 17, 2005 (closed book).
- Location: room 103 of the CSIE building.
- The examination will cover the lecture notes starting from p. 336
(November 8, 2006).
- 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.
-
There will be a final exam on January 18, 2005 (closed book).
- Location: rooms 103 and 104 of the CSIE building (but meet
in room 103 first).
- The examination will cover the lecture notes starting from p. 336
(November 8, 2006).
- 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.
-
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).