Złożoność obliczeniowa
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Sylabus
Autor
Maciej Ślusarek
Zawartość:
Złożoność obliczeniowa w modelu Maszyny Turinga, warianty modelu (off-line, wielotaśmowa, niedeterministyczna).
Inne modele dla złożoności: maszyna RAM - kryterium jednostajne i logarytmiczne, obwody logiczne. Zależności między funkcjami złożoności w poszczególnych modelach. Problem decyzyjny w notacji "naturalnej", kodowanie problemu.
Klasy złożoności, relacje między klasami. Twierdzenia o przyspieszaniu. Twierdzenia o hierarchii pamięciowej i czasowej. Domkniętość ze względu na dopełnienie.
Redukcje (wielomianowa, logarytmiczna, Turinga). Pojęcie zupełności. Klasa NP, NP-zupełność, twierdzenie Cooka-Levina.
Dowody NP-zupełności, techniki konstrukcji redukcji wielomianowych, analiza złożoności podproblemów, problemy liczbowe i silna NP-zupełność.
Algorytmy aproksymacyjne. Schematy aproksymacyjne.
Dolne ograniczenia na aproksymowalność. L-redukcje. Klasa MAXSNP, problemy MAXSNP-zupełne. Charakteryzacja klasy NP przez weryfikatory. Twierdzenie PCP i przykłady zastosowania do nieaproksymowalności.
Algorytmy probabilistyczne. Rozpoznawanie liczb pierwszych. Probabilistyczne klasy złożoności.
Modele obliczeń równoległych, klasy NC i RNC.
Klasy złożoności pamięciowej. Struktura klasy LOGSPACE. Hierarchia wielomianowa. Problemy zupełne w klasie PSPACE. Alternacja i gry.
Złożoność zliczania. Klasa #P.
Kryptografia a złożoność. Funkcje jednokierunkowe. Protokoły interaktywne. IP=PSPACE.
Literatura
1 Złożoność obliczeniowa, Christos H. Papadimitriou, Wydawnictwa Naukowo-techniczne, 2002.
2 Wprowadzenie do teorii automatów, języków i obliczeń, John E. Hopcroft, Jeffrey D. Ullman, Wydawnictwo naukowe PWN, 1994.
3 Computers and Intractability A Guide to the Theory of NP-completeness, Michael R. Garey, David S. Johnson, Freeman, 1979.
4 Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.
