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

Autor

Maciej Ślusarek

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

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