- Wykład Bartosza Klina: wtorki, 12-14, s. 5440
- Wykład Damiana Niwińskiego: środy, 12-14, s. 4070
Zasady zaliczania:
- Za zadania domowe można otrzymać maksymalnie 1.5 punktu.
- Za kolokwium można otrzymać maksymalnie 1.5 punktu.
- Nie ma progu zaliczenia ćwiczeń; każdy może podejść do egzaminu w pierwszym terminie.
- Za egzamin w pierwszym terminie można uzyskać maksymalnie 3 punkty.
- Ocena w pierwszym terminie będzie sumą punktów za prace domowe, kolokwium i egzamin.
- Za egzamin poprawkowy można uzyskać maksymalnie 4.5 punktu.
- Ocena w drugim terminie będzie sumą punktów za prace domowe i egzamin poprawkowy.
Prace domowe:
Będą trzy, wspólne dla całego roku. Rozwiązania proszę oddawać przez e-mail, do prowadzących ćwiczenia.- Praca nr 1. Termin oddawania rozwiązań: niedziela, 24 kwietnia.
- Praca nr 2. Termin oddawania rozwiązań: niedziela, 15 maja.
- Praca nr 3. Termin oddawania rozwiązań: niedziela, 19 czerwca.
Materiały:
- Damian Niwiński, Computational Complexity: lecture notes.
- Zbiór zadań MIMUW (powoli rosnący).
- Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993.
Wydanie polskie: Zlozonosc obliczeniowa, WNT 2002. - Dexter Kozen, Theory of Computation, Springer, 2006.
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 (draft).
- Oded Goldreich, P, NP, and NP-Completeness. The Basics of Complexity Theory, Cambridge University Press, 2010 (draft).
Program wykładów B. Klina:
Na powtarzające się prośby studentów, poniżej umieszczam linki do własnych notatek do wykładów. Nie gwarantuję, że nie ma w nich błędów lub przeinaczeń. Będę bardzo wdzięczny za zgłaszanie wykrytych pomyłek i/lub miejsc, w których przydałyby się dokładniejsze wyjaśnienia.
1 marca (notatki):
- definicja maszyny Turinga
- miary złożoności: czas i pamięć
- podstawowe klasy: P, EXPTIME, L, PSPACE
8 marca (notatki):
- twierdzenie Sipsera
- funkcje czasowo i pamięciowo konstruowalne
- twierdzenia o hierarchii czasowej i pamięciowej
15 marca (zastępstwo z W. Czerwińskim) (notatki):
- twierdzenie o luce czasowej
- obwody logiczne
22 marca (notatki):
- maszyny Turinga z poradą, klasa P/poly
- klasy ACi, NCi
5 kwietnia (notatki):
- twierdzenie: problem parzystości nie jest w klasie AC0
12 kwietnia (notatki):
- obliczenia niedeterministyczne
- klasy NTIME(f(n)), NSPACE(f(n)) i ich podstawowe własności
- twierdzenie Savitcha
19 kwietnia (notatki):
- redukcje i zupełność
- twierdzenie Cooka: NP-zupełność problemu SAT
- P-zupełność problemu HORN-SAT
- PSPACE-zupełność problemu QBF
26 kwietnia (notatki):
- NL-zupełność problemu osiągalności w grafie skierowanym
- twierdzenie Immermana-Szelepcsenyiego
- twierdzenie Ladnera o problemach pośrednich w NP
- twierdzenie Baker-Gill-Solovay o wyroczniach dla P vs. NP
17 maja (notatki):
- twierdzenie Baker-Gill-Solovay - dokończenie
- obliczenia randomizowane: klasy RP, PP, BPP
- problem niezerowości wielomianu jako przykład problemu w RP
24 maja (notatki):
- klasa ZPP
- metody derandomizacji
31 maja (notatki):
- fixed parameter tractability
- problemy optymalizacyjne i ich aproksymacja
7 czerwca (notatki):
- dowody interaktywne
- IP=PSPACE
14 czerwca (notatki):
- twierdzenie PCP