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.

• 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
  • probabilistyczne klasy złożoności,
  • rozpoznawanie liczb pierwszych.

• Modele obliczeń równoległych, klasy NC i RNC.

• Problemy funkcyjne i złożoność zliczania
  • klasy FP i FNP,
  • klasa 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 PSPACE-zupełne,
  • gry.
• 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

• Obliczenia w modelu maszyny Turinga

Moduł 2

• Klasy złożoności obliczeniowej

Moduł 4

• Problemy NP-zupełne

Moduł 6

• Algorytmy aproksymacyjne (ćwiczenia)
• Schematy aproksymacji i klasa MAXSNP (ćwiczenia)
• Twierdzenie PCP
• Algorytmy probabilistyczne

Moduł 11

• Problemy funkcyjne i złożoność zliczania
• Pamięć logarytmiczna i hierarchia wielomianowa
• Pamięć wielomianowa i złożoność wykładnicza

Moduł 15