Celem wykładu jest przedstawienie kluczowych koncepcji i twierdzeń teorii
złożoności obliczeniowej, ktore powinien znać każdy dobrze wykształcony
magister informatyki. Po uporządkowaniu wiedzy nabytej na JFiZ, przedstawimy
trochę podstawowych pojęć i faktow, a następnie przejdziemy do omawiania
zagadnień z poniższej listy.
* Pamięć vs Czas
* Twierdzenie Hopcrofta, Paula, Valianta: o tym, że pamięć jest cenniejszym zasobem niż czas obliczeń i że można przekonać się o tym grając w kamyki
* Dopełnienie vs Niedeterminizm
* Twierdzenie Immermana-Szelepcsenyi'ego: o tym, że niedeterministycznie można nie tylko zgadywać istnienie rozwiązań, ale także ich nieistnienie
* Determinizm vs Niedeterminizm
* Twierdzenie Paula, Pippengera, Szemeredi'ego i Trottera: o tym, że umiejętność zgadywania jest istotnie pomocna (przynajmniej wtedy, gdy mamy mało czasu)
* Struktura zbiorow NP-trudnych
* Twierdzenie Mahaneya: o tym, że zbiory NP-zupełne nie mogą mieć mało elementow, no chyba, że P=NP (w co nikt nie wierzy)
* Dowody interakcyjne
* Twierdzenie Shamira (IP=PSPACE): m.in. o tym, że ograniczony (w mocy obliczeniowej) krol Artur może skorzystać podczas gry w szachy z podpowiedzi nieskończenie mądrego Merlina i, co ważniejsze, nie dać mu się oszukać
* Trudność zliczania
* Twierdzenie Valianta: o znaczeniu „-1" w definicji wyznacznika macierzy albo inaczej o tym , że obliczanie permanentu macierzy jest nieporownanie trudniejsze od obliczania wyznacznika (no chyba, że P=NP:-)
* Twierdzenie Tody, o tym, że umiejętność szybkiego zliczania cykli Hamiltona w grafie ma daleko większe konsekwencje niż mogłoby się to wydawać
* Twierdzenie Valianta, Vazirani'ego o tym, że szukanie igły w stogu siana jest tak samo trudne niezależnie od liczby igieł w stogu (przynajmniej wtedy, gdy igłami są podstawienia spełniające formułę SAT, a stog tworzą podstawienia niespełniające)
* Algorytmy probabilistyczne:
* Twierdzenie Beigela, Reingolda, Spielmana: o tym jak policzyć przekonanych w więcej niż w 50%
* Złożoność problemu rozpoznawania liczb pierwszych
* Twierdzenie Pratta (Primes \in NP) o tym, że istnieją proste dowody pierwszości liczb,
* Twierdzenie Agrawala-Kayala-Saxeny (Primes \in P) o tym, że warto uczyć się algebry, by dowodow na pierwszość nie trzeba było zgadywać
* Spojność w grafach
* Twierdzenie Reingolda: o tym, że łatwiej jest sprawdzać połączenia, gdy drogi są dwukierunkowe
* Moc probabilistycznej weryfikacji
* Twierdzenie Arory, Safry o tym, że do nabrana przekonania o spełnialności formuły wystarczy wylosować stałą liczbę bitow z pewnego dowodu
Większość z powyższych twierdzeń udowodnimy. W niektorych przypadkach będziemy
jednak musieli zadowolić się przedstawieniem jedynie idei dowodu L
