Homework 3 will be handed out on the last lecture. There will be no
oral exam for that problem set.
Monday 17/5 is full.
Times available on Tuesday 18/5.
Homework 2 is due this week. Starting Wednesday it will be
possible to reserve time for your presentation.
Fredrik Niemelä is sick. Those who have made a reservation for today
will have to reschedule. I'm sorry for any trouble this causes.
Uppgift 6 i omgång 2: Man behöver något NP-fullständigt problem som
kan anses vara "känt". Ni får använda valfritt NP-fullständigt problem
som för vilket det i Papadimitrious bok finns ett bevis för
Uppgift 2 upplagd. Versionen som delades ut på dagens föreläsning var fel! Rättad
version finns via länken ovan.
Redovisningstider kan bokas under länken
En fix till problem 7 på omgång 1 finns på webbsidan
"uppgifter". Eventuella ytterligare fixar till denna eller andra
omgångar kommer att dyka upp där.
Nu finns en "newsgroup": nada.kurser.kplx04. Den är ett bra forum för
frågor om exempelvis uppgifterna eftersom rättelser och
förtydliganden når alla.
Uppgiftsomgång 1 finns nu under "uppgifter".
In some cases I will include my
my lecture notes from a previous year. They
are available as pdf files thanks to Mattias Amnefelt.
Take them for what they are: notes I prepared for myself. Beware of errors
and omissions as well as my handwriting.
040316, lecture 1
parts of chapters 2 and 3. Administration. Solving computational problems
using bounded resources.
Turing machines: definition and examples (palindromes). Definitions of
computability, decidability and recursive enumerability. The classes R
(recursive languages) and RE (recursively enumerable languages). Church's
040317, lecture 2
More from chapters 2 and 3,
Multi-tape TMs. Encoding TM as a string. Universal TM. R, RE, coRE,
R = (RE intersect coRE). Showed that there is a TM that enumerates L iff
there is a TM that accepts L. Defined non-deterministic TM and what it
means for it to accept input x in k steps. Showed the existence of
undecidable problems and that the Halting language is in RE but not in R.
040317, lecture 3
Concluded chapters 2 and 3, parts of
Chapter 7. RE-complete problems and man-one-reductions.
Defined TIME(f(n)) and SPACE(f(n)) and corresponding for
non-deterministic computation. Linear speed-up (and corresponding
result for space). Defined the classes L, NL, coNL, P, NP,
coNP, PSPACE, NPSPACE, EXP, and stated some inclusion results.
040323, lecture 4
More of Chapter 7. Time- and
space-hierarchies. Thereom 7.4 and the connection between
nondeterministic space and the reachability problem.
040324, lecture 5
Chapter 7. Savitch's theorem. PSPACE =
NPSPACE. Defined logspace-reductions, NL-completeness and
coNL-completeness. Reachability NL-complete and Non-reachability
coNL-complete. NL = coNL (by showing that non-reacability is in
notes on reachability and NL=coNL.
040326, lecture 6
Chapter 8. Reductions and complete
problems. What it means for a class to be closed under
logspace-reductions. SAT and CLIQUE as examples of complete
problems. A detailed reduction of CLIQUE to SAT.
040326, lecture 7
Chapters 8 and 9.
NP-certificates and polynomially balanced
relations. Circuit value is P-complete, Circuit satisfiability and
3SAT are NP-complete.
040427, lecture 8
Chapters 9 and 10 + notes.
Proofs of NP-completeness for
Three-partite matching, Exact cover, and Knapsack. Defined coNP and
coNP-completeness. Example of problem in (NP intersect coNP) that is
not known to be in P: given (g,p), decide if p is prime and g is
generator of Zp*. (Notes, see below.)
040428, lecture 9
Chapters 9 and 10 + notes. Proof that
Zp* is cyclic when p is prime.
NP-function problems and NP-optimization problems. Oracle Turing
machines. If we have a SAT-oracle we can find a satisfying
assignment in polynomial time, and if we have an oracle for
graph colorability then we can find an optimal coloring in
polynomial time. The class FNP, reductions for FNP-problems, and
notes for lectures 8 and 9
040504, lecture 10
Chapter 11 (11.1 and 11.2).
machines. The classes RP, coRP, ZPP, and BPP. ZPP = (RP intersect
coRP). A in ZPP iff A can be decided in expected polynomial time.
Error reduction for RP and coRP.
040505, lecture 11
Chapter 11 (11.1 and 11.2), and a
handout (5 pages from Sipser's Introduction to the Theory of
Error reduction for BPP. Chernoff bounds.
Proof that equivialence Read-once brancing programs is in coRP.
040511, lecture 12
PSPACE. PSPACE complete
problems: Generalized geography, QSAT.
Chapter 13 (pages 299-313). Approximation of
NPO-problems. Approximation ratio and ε-approximation.
040512, lecture 13
More about approximation of NPO-problems. Approximation algorithm for
Max3SAT and FPTAS for Knapsack. Non-approximability of general
TSP. L-reductions (preserve approximability).
040518, lecture 14
Overview of some complexity classes: PP, parity-P, #P. Polynomial
hierarchy (PH). Introduction to interactive proofs and the class
IP. IP contains NP but also problems that are (probably) not in NP
such as Graph Non-isomorphism. PSPACE contains IP (sketch of proof).
040519, lecture 15
Claimed that PSPACE=IP. Proved weaker result that P#P is
contained in IP. This implies that IP contains coNP, and by a result
of Toda that IP continains the polynomial hierarchy.