Złożoność obliczeniowa 2014/2015

Egzamin

Materiały

Najważniejsze zagadnienia

1. Co to jest uniwersalna maszyna Turinga?
2. Co to jest problem decyzyjny, problem funkcyjny, klasa złożoności? Podstawowe inkluzje między klasami.
3. Co to jest obwód logiczny i jak może symulować maszynę Turinga?
4. Co to jest jednorodna rodzina obwodów i jak się ma do obliczeń równoległych?
5. Jak działają niejednorodne modele obliczeń: obwody i maszyny?
6. Co mówi twierdzenie o hierarchii?
7. Co to jest klasa NP? (porównanie definicji) Jakie problemy zawiera, jakich nie?
8. Co to znaczy, ze problem jest NP-zupelny? Dlaczego istnieje choć jeden taki?
9. Jak działa algorytm Savitcha symulujący niedeterministyczną maszynę Turinga?
10. Co to znaczy, ze problem jest PSPACE-zupelny? Jakie są przykłady takich problemów?
11. Do czego służą redukcje w pamięci logarytmicznej? Przykłady problemów zupełnych dla klas NL i P.
12. Jak rozstrzygać nieosiągalność w NL (tw. Immermana-Szelepcsenyiego)?
13. Co to znaczy, że problem da się efektywnie rozwiązać algorytmem randomizowanym? (definicja probabilistycznej maszyny Turinga i klasy BPP)
14. Do czego służy amplifikacja i jak działa?
15. Jak się do siebie mają klasy PP, BPP, RP, co-RP i ZPP?
16. Co to znaczy zderandomizować? Co wiadomo o derandomizacji w modelu jednorodnym, a co w niejednorodnym?
17. Co to jest IP? (definicja i przykłady)
18. Jak działa metoda algebraizacji i do czego słuzy?
19. Jak sobie radzić z problemami NP-trudnymi, dokladnie i mniej wiecej?
20. Jak dowodzić nieaproksymowalności? (Twierdzenie PCP)

Ogólne reguły dotyczące zadań domowych

• Rozwiązanie należy przesłać pocztą elektroniczną na adres wskazany w treści zadania.
• Temat wiadomości powinien być dokładnie taki, jak temat listu informującego o pojawieniu się pracy domowej.
• Rozwiązanie powinno być pojedyńczym plikiem PDF o nazwie: ZLOi-numerIndeksu.pdf, gdzie i jest liczbą 1, 2, 3, lub 4, odpowiadającą numerowi zadania.
• Wewnatrz pliku proszę podać imię, nazwisko, numer indeksu.
• Zachęcamy Państwa do redagowania rozwiązań w latexu, ale nie nalegamy.
• W wyjątkowych okolicznościach dopuszczamy możliwość wysłania zdjęcia lub skanu rozwiązania napisanego ręcznie na papierze.
• Dwukrotne skorzystanie z powyższej możliwości jest raczej nadużyciem.