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 badań 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
• Przemysław Broniek - Uniwersytet Jagielloński
• Grzegorz Gutowski - Uniwersytet Jagielloński
• Jan Jeżabek - Uniwersytet Jagielloński

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 $\oplus {\text{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. C.H. Papadimitriou, Złożoność obliczeniowa, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.
2. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa 1994.
3. M.R. Garey, D.S. Johnson, Computers and Intractability A Guide to the Theory of NP-completeness, Freeman, 1979.
4. M. Sipser, Introduction to the Theory of Computation, 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)