Teoria złożoności 1000-2M04TZ

Intuicja złożoności znana z życia codziennego zyskuje ścisły sens w wielu współczesnych naukach przyrodniczych (chemii, biologii), a także w naukach o człowieku. W informatyce złożoność jest miarą trudności problemu obliczeniowego, wyrażoną w ilości zasobów (przede wszystkim czasu) koniecznych do jego rozwiązania.
Teoria złożoności jest dziedziną komplementarną do algorytmiki. Podczas gdy algorytmika poszukuje najbardziej ekonomicznych rozwiazań, teoria złożoności próbuje wyjaśniać, dlaczego niektóre problemy okazują sie odporne na próby znalezienia dobrych algorytmów i klasyfikuje problemy obliczeniowe ze względu na ich trudność. Jednak ścisłe dowody nieistnienia "dobrych pomysłów'' algorytmicznych leżą jak się wydaje na granicy możliości współczesnej matematyki, stąd w teorii złożoności wciąż jest więcej hipotez niż pewników.
Celem wykładu jest wprowadzenie słuchaczy w tę fascynującą problematykę, której znajomość jest niezbędna w pracy naukowej w jakiejkolwiek dziedzinie informatyki teoretycznej, ale jest także przydatna w pracy informatyka - praktyka (architekta systemu, analityka, programisty).

Plan wykładu:
1. Podstawowe modele obliczeń: maszyna Turinga, maszyna RAM, oraz obwody logiczne.
2. Granice obliczalności: problemy nierozstrzygalne, twierdzenie Rice'a, typy redukcji, stopnie nierozstrzygalności.
3. Złożoność czasowa i pamięciowa, nieskończona hierarchia trudności problemów.
4. Obliczalność wielomianowa, jej charakteryzacja poprzez gry, problemy P-zupełne.
5. Siła obliczeń niedeterministycznych, twierdzenie Immermana-Szelepscenyiego, klasa NP.
6. Problemy NP-zupełne, hipoteza P=NP, aproksymowalność.
7.Obwody monotoniczne i twierdzenie Razborowa o nierozwiązywalności problemu kliki w tym modelu.
8. Klasa PSPACE i interakcyjne modele obliczeń: maszyny alternujące, dowody interakcyjne i gry z naturą.
9. Klasy złożoności modeli niejednorodnych: AC0, TC0, NC1 i ograniczenia dolne.
10. Obliczenia zrandomizowane, probabilistyczne klasy złożoności i derandomizacja.
11. Klasy liczące, problem permanentu.
12. Kwantowe modele obliczeń i klasy złożoności.

Założenia:
1000-215JAO