Złożoność obliczeniowa

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Autor

Maciej Ślusarek

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.