Złożoność obliczeniowa

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

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

Złożoność obliczeniowa, Christos H. Papadimitriou, Wydawnictwa Naukowo-techniczne, 2002.

Wprowadzenie do teorii automatów, języków i obliczeń, John E. Hopcroft, Jeffrey D. Ullman, Wydawnictwo naukowe PWN, 1994.

Computers and Intractability A Guide to the Theory of NP-completeness, Michael R. Garey, David S. Johnson, Freeman, 1979.

Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.