Last homework set was handed out yesterday. for this set, only your
written solutions will be graded (no chance to clarify during an oral
presentation), so take care to make clear and complete.
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.
040510
Homework 2 is due this week. Starting Wednesday it will be
possible to reserve time for your presentation.
040505
Fredrik Niemelä is sick. Those who have made a reservation for today
will have to reschedule. I'm sorry for any trouble this causes.
040503
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
NP-fullständighet.
040427
Uppgift 2 upplagd. Versionen som delades ut på dagens föreläsning var fel! Rättad
version finns via länken ovan.
040419
Redovisningstider kan bokas under länken
Uppgifter.
040323
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.
040322
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.
040318
Uppgiftsomgång 1 finns nu under "uppgifter".
Lecture log
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
Chapter 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
thesis. Notes
from 2002
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.
Notes
from 2002
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
NL). Some
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.
Notes
from 2002
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
FNP-completenes.
Some
notes for lectures 8 and 9
040504, lecture 10
Chapter 11 (11.1 and 11.2).
Probabilistic Turing
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
Computation).
Error reduction for BPP. Chernoff bounds.
Proof that equivialence Read-once brancing programs is in coRP.
040511, lecture 12
Chapter 19.1.
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.
