Złożoność obliczeniowa 2011/12

Pytania egzaminacyjne

1. Tw. o hierachii pamięciowej
2. Tw. Savitcha
3. Tw. Cooka
4. NP-zupełność trójwymiarowego skojarzenia lub NP-zupełność cyklu Hamiltona
5. NP-zupełność (tak/nie) podproblemów SAT: 2SAT, 3SAT, 3OCCUR-3SAT, NAE-SAT oraz ich wersji MAX-...
6. Silna NP-zupełność, poprawność dowodów za pomocą redukcji pseudowielomianowej, NP-zupełność izomorfizmu podgrafu (lasu) drzewa
7. Algorytm aproksymacyjny dla problemu pokrycia zbiorami
8. FPTAS dla problemu plecakowego
9. PTAS dla problemu najkrótszego uszeregowania
10. Silna NP-zupełność a istnienie FPTAS
11. Aproksymacja problemu MAX-k-FSAT
12. L-redukcja MAX-k-FSAT do MAX3SAT
13. Klasa MAXSNP, przynależność MAX2SAT, k-IS, k-VC, MAX-CUT
14. MAX3SAT jest MAXSNP-zupełny
15. Równoważność tw. PCP oraz istnienia redukcji wprowadzającej lukę z SAT do MAX3SAT.
16. Twierdzenie Immermana-Szelepcsenyi'ego
17. NP, co-NP, tw. Ladnera, hierarchia wielomianowa, problemy zupełne w warstwach hierarchii i w PSPACE