Zaawansowane aspekty złożoności obliczeniowej 1000-2M24ZAZ
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.
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
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ć.
Kryteria oceniania
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ą.
Literatura
• 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)
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: