Skolan för datavetenskap och kommunikation


  arrow rigth  



2D1446 Komplexitetsteori



Times for oral presentation on 25/5.

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.

An evaluation form (in Swedish) is available.


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 NP-fullständighet.


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 Uppgifter.


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".

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.

Sidansvarig: Mikael Goldmann <migo@nada.kth.se>
Uppdaterad: 2004-06-04