Lecture 04: Mon, Jan 29. Wrap up of automata
theory. Introduction to Turing machines. Recursive and recursively
enumerable languages. Read: Sipser, chap. 3.
Lecture 05: Wed, Jan 31. Variations of Turing machines
including non-determinism. Church-Turing Thesis. Examples of Decidable
Languages. Universal Turing Machine. Halting Problem. Undecidability.
Read: Sipser, chap. 4.
Lecture 06: Mon, Feb 05. R is the intersection of
RE and coRE. Examples of undecidable
problems. Techniques to show undecidability: Turing reductions,
mapping reductions, Rice's theorem. How to show a language is not
RE/coRE. Read: Sipser, chap. 5, Papadimitriou, chap. 3.
Lecture 07: Wed, Feb 07. Method of Configuration
Histories. Undecidability of some CFG problems, Post's Correspondence
Problem. Recursion Theorem. Problem Set 2
out (on computability, due Friday Feb. 23). Read: Sipser,
end of Chap. 5, beginning of chap. 6.
Lecture 08: Mon, Feb 12. More on Recursion
theorem. Mentioning of Advanced Topics in Computability (arithmetic
hierarchy, complete problems, Recursive inseparability, Kolmogorov's
complexity). Wrap-up of Computability. Introduction to Logic
(propositional calculus). Read: Sipser, finish chap. 6,
Papadimitriou, skim chap. 4.
Lecture 09: Wed, Feb 14. First-Order logic. Models and
Interpretations. Tautologies and unsatisfiable sentences. Prenex
Normal Form, Skolemization, Universal Formulas, Herbrand's
Theorem. Read: Papadimitriou, beginning of chap. 5.
No class Mon, Feb 19, President's day.
Lecture 10: Wed, Feb 21 R.e. test for universal
tautologies, undecidability of universal tautoligies (Church-Turing
Theorem), compactness theorem, Lowenheim-Skolem theorem,
axiomatizable theories and their recursive enumerability, Godel
completeness theorem.Read: Papadimitriou, chap. 5.
Lecture 11: Fri, Feb 23 (substitute for
Mar. 19). (Un)decidability of specific models, model of number
theory. Peano Arithmetic. Godel's incompleteness theorem and
extensions. Limitations of First-Order Logic. Introduction to
descriptive complexity. Wrap-Up of Logic. Problem Set 3 out (on logic, due Monday
Mar. 5). Read: Sipser, sec. 6.2, Papadimitriou, chap. 6.
Lecture 12: Mon, Feb 26. Time Complexity. Linear speedup.
Universality of polynomial time. Class P, Examples of problems
in P. Class NP, examples of problems in
NP. P vs NP question.Read: Siser, sec 7.1-7.3,
Papadimitriou, sec. 2.4.
Lecture 13: Wed, Feb 28. Reductions and
NP-Completeness. Cook-Levin Theorem. Examples of
NP-complete problems. Read: Sipser, sec. 7.4-7.5,
Papadimitriou, chap. 8-9.
Lecture 14: Mon, Mar 05. More NP-complete
problems. Search Classes FP and FNP, completeness of
FSAT, self-reducibility of SAT, FP=FNP iff
P=NP. Class TFNP of total search problems
(factoring). NP-hardness, class coNP,
NP=coNP question, impossibility of NP-hardness in
TFNP (e.g., factoring). Problems in NP intersection
coNP (primality). Read: Papadimitriou, chap. 10.
Lecture 15: Wed, Mar 07. More on NP intersection
coNP. Primality in NP intersection
coNP. Mincut/Maxflow theorem. Structure of NP-complete
problems. Ways to deal woth NP-completeness: randomization,
input restrcitions, average-case analysis and approximation
algorithms. Examples of Approximation algorithms for
NP-complete problems. Problem Set 4
out (on P, NP, NP-completeness, optimization
problems, due Friday Mar. 28). Read: Papadimitriou, more chap. 10,
14.1-14.2, Sipser, sec. 10.1
No classes Mar 12-16, spring break.
No classes Mar 19-23, 2 substitute classes (Feb 23 and
April 6).
Lecture 16: Mon, Mar 26. Space Complexity. General
relations between space and time. Reachability method. Savitch's
theorem. Classes PSPACE and NPSPACE, their equality.
NP in PSPACE. Read: Sipser, sec. 8.1-8.2,
Papadimitriou, sec. 7.3
Lecture 17: Wed, Mar 28. PSPACE-completeness. Some
complete problems: TQBF, Generalized Geography, Emptiness of L(NFA).
Winning strategies for Games. Read: Papadimitriou, sec. 19.1,
Sipser, sec. 8.3
Lecture 18: Mon, Apr 02. Sublinear space
model. Logarithmic space. Classes L and NL. Log-space
reductions. NL-complete problems (REACHABILITY,
2SAT). NL = coNL. Problem Set 5
out (on space complexity, due Wednesday Apr. 11). Read:
Papadimitriou, sec. 16.1, Sipser 8.4-8.5.
No class on Wed, Apr 04. Substitute on Fri, Apr 20.
Lecture 19: Fri, Apr 06. Related topics: (1)
P-completeness (circuit value problem); (2) Oracle separations
of P and NP; (3) time and space hierarchy theorems (as
corollaries, separation of P and EXP, NL and
PSPACE). Read: Sipser, end of sec. 10.5, sec. 9.1, 9.2,
9.3, Papdimitriou, sec. 7.2, 8.2, 14.3.
Lecture 20: Mon, Apr 09. Randomized Computation and its
importance. Class BPP. Aplification lemma for
BPP. Randomized test for primality. Schwartz-Zippel lemma,
randomized test for polynomial identity. Applications: (1) testing
equivalence of read-once branching programs; (2) efficient
communication protocol for testing string equality. Read: Sipser,
sec. 10.2.
Lecture 21: Wed, Apr 11. Other randomized complexity
classes: PP, RP, coRP and ZPP. ZPP
equals RP intersection coRP. Primality belongs to
ZPP (sketch). Inadequacy of PP (NP belongs to
PP). RP belongs to NP intersection
BPP. Class P/poly (languages having non-uniform
polynomial size circuits). RP belongs to P/poly. Ideas
of random walk (randomized algorithm for 2SAT). Read:
Papadimitriou, sec. 11.1, 11.2, 11.4.
Lecture 22: Mon, Apr 16. BPP belongs to
P/poly. Same result is unlikely for NP (see below).
Polynomial hierarchy PH. Existence of complete problems for
various levels of PH (all special cases of TQBF). Containment
in PSPACE. Standard assumption: PH does not
"collapse". NP does not belong to P/poly under this
assumption. BPP belongs to the second level of the
hierarchy. Mention Toda's theorem: PH belongs to
P^PP. Problem Set 6 out (on
randomization and interactive protocols, due Wednesday Apr. 25).
Read: Papadimitriou, sec. 11.4, 17.2.
Lecture 23: Wed, Apr 18. Randomized space-bounded
complexity classes (BPL, RL, coRL,
ZPL). Always halting versus non-always halting classes
(non-always halting radomized classes all collapse to NL).
Random walks on graphs, cover times. Test for undirected connectivity:
USTCONN belongs to RL (mention can extend to ZPL, also
that belongs to SPACE(log^{4/3} n)). Is randomness necessary?
Derandomization techniques: (1) specific (method of conditional
probabilities, example for MAX3SAT), (2) general (pseudorandom
generators); (3) weaken the assumption of perfect unbiased randomness
(imperfect random sources, von Newman trick, slightly random sources).
Survey of space-bounded derandomization: Nisan's generator, BPL
belongs to TIMESPACE(poly(n),log^2 n) (mention BPL
belongs to SPACE(log^{3/2} n)), Nisan-Zuckerman generator
(randomness is linear in space), conjecture that L=BPL (and
different from NL). Brief survey on time-bounded
derandomization: pseudorandom generators using cryptography, hardness
vs. randomness (P=BPP unless every problem in E has
subexponential size circuits). Read: Papadimitriou, Sec. 13.1
(example of MAX3SAT), 11.3, 16.3, Saks survey
Lecture 24: Fri, Apr 20. Introduction to interactive
protocols. Class IP, GNI example. Zero-knowledge, class
PZK, GI example. Read: Sipser, Sec. 10.4, Papadimitriou,
pp. 289-293, sec. 19.2, Goldreich's lectures
Lecture 25: Mon, Apr 23. IP=PSPACE (Shamir's
theorem). Arthur-Merlin games, class AM. Private coins = public
coins: IP(r) belongs to AM(r+2). Collapse theorem:
AM(r) belongs to AM(r/2). Universality of AM.
Multiple provers, class MIP. MIP=NEXP. coNP in
AM implies the hierarchy collapses. Read: Sipser,
sec. 10.4, Papadimitriou, pp. 474-480, pp. 506-508, lecture notes,
Goldreich lectures
Lecture 26: Wed, Apr 25. Refereed games and conflicting
provers (class RG). RG=EXP. Rounds and private/public
coins: RG(1,private) = PSPACE = RG(poly,public). Oracles
vs. provers, class PCP. PCP=MIP=NEXP. Property testing
using oracles. PCP-characterization of NP:
NP=PCP(O(log n), O(1)). Applications to inapproximability.
Read: Papadimitriou, sec. 13.3, lecture notes, Goldrecih's
lectures, Feige/Kilian paper
Lecture 27: Mon, Apr 30. Cryptography and complexity. Basic
primitives: one-way functions/permutations, trapdoor
functions/permutations. Examples (multiplication, modular
exponentiation, RSA). Why P<>NP is necessary but not sufficient
for cryptography (e.g., one-way functions). Read: Sipser,
sec. 10.6, Papadimitriou, chap. 12