Zaawansowane aspekty złożoności obliczeniowej

Złożoność obliczeniowa 1000-218bZO

Teoria złożoności klasyfikuje problemy obliczeniowe ze względu na ich trudność i tłumaczy, dlaczego niektóre problemy okazują się odporne na próby znalezienia dobrych algorytmów. Przedmiot ten jest kontynuacją przedmiotu „Złożoność obliczeniowa”. Poruszymy klasyczne tematy teorii złożoności, które nie zmieściły się na tamtym przedmiocie.

1) Hierarchia wielomianowa. Nie da się rozwiązać SAT w czasie liniowym i podliniowej pamięci.

2) Twierdzenia Karpa-Liptona i Meyera – hierarcha wielomianowa a niejednorodne obwody.

3) BPP a hierarchia wielomianowa.

4) Hierarchia wielomianowa a problemy zliczania. Twierdzenie Tody.

5) Dowody interaktywne – alternatywna definicja pamięci wielomianowej.

6) Bezpieczeństwo obliczeniowe, funkcje jednokierunkowe i generatory liczb pseudolosowych.

7) Podstawy obliczeń kwantowych.

8) Twierdzenie PCP i trudność aproksymacji.

9) Złożoność dowodowa.

10) Ekspandery i ich użycie w generatorach pseudolosowych.

11) Dowody naturalne.

12) Złożoność obliczeniowa a logika. Twierdzenia Fagina i Immermana-Vardiego.

• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press 2009 (dostępne on-line)

Wiedza

Student pogłębia wiedzę o klasycznych zagadnieniach teorii złożoności. (K_W01)

Umiejętności

Student potrafi konstruować rozumowania matematyczne dotyczące klas złożoności obliczeniowej. (K_U01)

Student potrafi identyfikować przynależność i trudność wybranych problemów obliczeniowych w stosunku do ważnych klas złożoności, wykorzystując ich różne charakteryzacje. (K_U05)

Kompetencje

Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii złożoności i potrafi z nich korzystać.

Egzamin ustny. Dodatkowo, możliwe podwyższenie oceny dzięki rozwiązaniu zadań gwiazdkowych. Każde zadanie warte jest 1 podzielone przez liczbę studentów, którzy prawidłowo je rozwiązali.

Dla doktorantów: obowiązkowe wzięcie udziału w rozwiązywaniu zadań gwiazdkowych, albo zapoznanie się z najnowszą literaturą.