Złożoność obliczeniowa 2009/10
Pytania egzaminacyjne
Wymagany jest stopień szczegółowości opisu algorytmu pozwalajacy bez wątpliwości zanalizować jego złożoność. Analiza poszczególnych algorytmów i dowody twierdzeń obowiązują w zakresie jak na wykładzie.
- Twierdzenie o liniowej kompresji i o liniowym przyspieszaniu
- Tw. o hierachii pamięciowej
- Tw. Savitcha
- Tw. Cooka
- NP-zupełność trójwymiarowego skojarzenia
- NP-zupełność cyklu Hamiltona
- NP-zupełność trójkolorowania, dowód dla wersji ogólnej oraz dla grafów o ograniczonym stopniu wierzchołka
- Silna NP-zupełność, dowodzenie za pomocą transformacji pseudowielomianowej i jego poprawność; definicja dla modelu MT
- Silna NP-zupełność szeregowania w przedziałach i izomorfizmu podgrafu (lasu) drzewa
- Algorytmy aproksymacyjne: 2-MST i 3/2-MST dla problemu komiwojażera,
1/2OPT dla plecaka, 2OPT dla najkrótszego uszeregowania
- Algorytm aproksymacyjny dla problemu pokrycia zbiorami
- FPTAS dla problemu plecakowego
- PTAS dla problemu najkrótszego uszeregowania
- Silna NP-zupełność a istnienie FPTAS
- Aproksymacja problemu MAX-k-FSAT
- L-redukcja MAX-k-FSAT do MAX3SAT
- Klasa MAXSNP, przynależność MAX2SAT, k-IS, k-VC, MAX-CUT
- MAXSNP-zupełność MAX3SAT
- Równoważność tw. PCP oraz istnienia redukcji wprowadzającej lukę z SAT do MAX3SAT.
- Klasy coNP, PH, PSPACE, - inkluzje, problemy zupełne
- Tw. NL=coNL