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 - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
• Przemysław Broniek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
• Grzegorz Gutowski - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
• Jan Jeżabek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,

Wymagania wstępne

Matematyka dyskretna, Algorytmy i struktury danych, Języki, automaty i obliczenia.

Zawartość

• Złożoność obliczeniowa w modelu maszyny Turinga
  • zasoby obliczeniowe
  • 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 różnych modelach

• 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

• Redukcje i zupełność
  • rodzaje redukcji: wielomianowa, logarytmiczna, Turinga
  • pojęcie zupełności
  • klasa NP, NP-zupełność, twierdzenie Cooka-Levina
  • charakteryzacja klasy NP w języku logiki

• Dowody NP-zupełności i analiza złożoności problemu
  • przykłady redukcji i techniki ich konstrukcji
  • analiza złożoności podproblemów
  • problemy liczbowe i silna NP-zupełność

• Algorytmy aproksymacyjne
  • wersje optymalizacyjne problemów decyzyjnych
  • przykłady algorytmów aproksymacyjnych
  • schematy aproksymacyjne

• Dolne ograniczenia na aproksymowalność
  • L-redukcje
  • klasa MAXSNP, problemy MAXSNP-zupełne
  • charakteryzacja klasy NP przez weryfikatory
  • twierdzenie PCP i przykłady jego zastosowania

• Algorytmy probabilistyczne
  • probabilistyczne klasy złożoności
  • rozpoznawanie liczb pierwszych
  • generowanie bitów losowych

• Obliczenia równoległe
  • modele obliczeń równoległych
  • klasy złożoności równoległej
  • P-zupełność
  • równoległość i randomizacja

• Problemy funkcyjne i złożoność zliczania
  • klasy FP, FNP, TFNP
  • klasa #P i twierdzenie Valianta
  • klasa Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \oplus\textsc{P}}

• Pamięć logarytmiczna i hierarchia wielomianowa
  • klasy L, NL i coNL
  • twierdzenie Immermana-Szelepcsényi'ego
  • klasy coNP i DP
  • maszyny alternujące
  • hierarchia wielomianowa

• Pamięć wielomianowa
  • klasa PSPACE, problemy zupełne
  • gry
  • problemy zwięzłe i złożoność wykładnicza

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

Moduły

1. Obliczenia w modelu maszyny Turinga (test)
2. Inne modele dla złożności (test)
3. Klasy złożoności obliczeniowej (test)
4. Redukcje i zupełność (test)
5. Problemy NP-zupełne (test)
6. NP-zupełność jako narzędzie analizy problemu (test)
7. Algorytmy aproksymacyjne (test)
8. Schematy aproksymacji i klasa MAXSNP (test)
9. Twierdzenie PCP i nieaproksymowalność (test)
10. Algorytmy probabilistyczne (test)
11. Obliczenia równoległe (test)
12. Problemy funkcyjne i złożoność zliczania (test)
13. Pamięć logarytmiczna i hierarchia wielomianowa (test)
14. Pamięć wielomianowa i złożoność wykładnicza (test)
15. Kryptografia a złożoność (test)