Computing Theory Course
Computing Theory
Time: 9:10--12:20 Tuesday
Location: Room 111
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
-
蔡芸琤 Tsai, Yun-Cheng (Pecu)
-
盧政良 Lu, Zheng-Liang
-
陸裕豪 Lok, U Hou
-
高哲遠 Gao, Zheyuan (Jeffrey)
-
龐德沙 Pontaza Rodas, Ricardo Neftali ("Panda")
-
TA Hours
-
14:00 ~ 17:00 on Tuesdays in room 446(蔡芸琤 Tsai, Yun-Cheng (Pecu))
-
13:00 ~ 15:00 on Wednesdays in room 446(盧政良 Lu, Zheng-Liang)
-
15:00 ~ 17:00 on Tuesdays in room 446(陸裕豪 Lok, U Hou)
-
15:00 ~ 17:00 on Thursdays in room 328(高哲遠 Gao, Zheyuan (Jeffrey))
-
13:00 ~ 15:00 on Wednesdays in room 446(龐德沙 Pontaza Rodas, Ricardo Neftali ("Panda"))
-
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. Homework can be written in Chinese or English. 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.
Time stamp will be used to determine if the homework is late or not. Beware of the potential email reliability problem.
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!
|
-
2013.09.10
-
2013.09.17
-
2013.09.24
-
2013.10.01
&
1st homework due
&
solutions
-
2013.10.08
-
2013.10.15
-
2013.10.22
&
2nd homework due
&
solutions
-
2013.10.29
-
2013.11.05
&
mid-term exam
&
solutions
-
2013.11.12
-
2013.11.19
&
3rd homework due
&
solutions
-
2013.11.26
-
2013.12.03
-
2013.12.10
&
4th homework due
&
solutions
-
2013.12.17
&
mid-term exam
&
solutions
-
2013.12.24
&
5th homework due
&
solutions
-
2013.12.31
-
2014.01.07
&
final exam
&
solutions
Examinations and grading
-
There is a mid-term exam on November 5, 2013 (closed book).
- Locations: Rooms 103, 105, 107 and 111 of the CSIE building.
-
To avoid congestion, you should take the test in the room based on your student ID number
as follows:
- R105 for r02922002 ~ r02922041.
- R107 for r02922043 ~ r02922077.
- R111 for r02922078 ~ r02922108.
- R103 for the rest.
- The examination will cover the lecture notes up to p. 322 (October 22, 2013),
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 mid-term exam on December 17, 2013 (closed book).
- Locations: Rooms 103, 105, 107 and 111 of the CSIE building.
-
To avoid congestion, you should take the test in the room based on your student ID number
as follows:
- R105 for r02922002 ~ r02922041.
- R107 for r02922043 ~ r02922077.
- R111 for r02922078 ~ r02922108.
- R103 for the rest.
- The examination will cover the lecture notes from
p. 312 through p. 427, 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 7, 2014 (closed book).
- Locations: Rooms 103, 105, 107, and 111 of the CSIE building.
-
To avoid congestion, you should take the test in the room based on your student ID number
as follows:
- R105 for r02922002 ~ r02922041.
- R107 for r02922043 ~ r02922077.
- R111 for r02922078 ~ r02922108.
- R103 for the rest.
- The examination will cover the lecture notes from
p. 428 through p. 759, 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.
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).