Złożoność obliczeniowa
Forma zajęć
Wykład (30 godzin) + ćwiczenia (30 godzin)
Opis
Złożoność obliczeniowa to dziedzina informatyki teoretycznej zajmująca się klasyfikacją języków formalnych ze względu na ilość zasobu - czasu i pamięci - potrzebnego do rozpoznawania języka. Ponieważ język formalny jest abstrakcyjnym odpowiednikiem problemu algorytmicznego, teoria ta dostarcza narzędzi do szacowania trudności obliczeniowej takich problemów. Niniejszy kurs zapoznaje uczestników z najważniejszymi rezultatami dotyczącymi klas złożoności, ich własności i wzajemnych zależności a także omawia wynikające z tych faktów wnioski dotyczące praktycznych problemów algorytmicznych.
Sylabus
Autorzy
- Maciej Ślusarek
- Przemysław Broniek
- Grzegorz Gutowski
- Jan Jeżabek
Wymagania wstępne
Matematyka dyskretna, Algorytmy i struktury danych, Języki, automaty i obliczenia.
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 obliczeniowej
- klasy złożoności czasowej i pamięciowej,
- twierdzenia o liniowym przyspieszaniu i kompresji pamięci,
- relacje między klasami, twierdzenie Savitcha i dopełnienia klas,
- twierdzenia o hierarchii czasowej i pamięciowej.
- 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
- rodzaje: 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.
- Problemy funkcyjne. Złożoność zliczania. Klasa #P.
Problemy funkcyjne i złożoność zliczania
- klasy FP i FNP,
- klasa TFNP,
- klasa Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{P}} i twierdzenie Valianta,
- klasa Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{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.
