Złożoność Obliczeniowa

Wykład: Krzysztof Loryś

Ćwiczenia: Krzysztof Loryś, Tibor Różański

Wykłady

· Wykład 1: Lemat o kompresji taśmy; Symulacja maszyn wielotaśmowych na maszynie jednotaśmowej; Konstruowalność funkcji (pamięciowa i czasowa); Twierdzenie o hierarchii taśmowej; Lemat o przyspieszaniu;

· Wykład 2: Symulacja maszyn wielotaśmowych na maszynie dwutaśmowej; Twierdzenie o hierarchii czasowej; Licznik Paula; Licznik Fürera; Hierarchia czasowa dla maszyn k-taśmowych;

· Wykład 3: Dolne ograniczenie pamięciowe na rozpoznawanie języków nieregularnych; Twierdzenie o luce; Gra w kamyki; DTIME(T)ÍDSPACE(T/logT);

· Wykład 4: cd: DTIME(T)ÍDSPACE(T/logT); Twierdzenie Savitcha; Lemat translacyjny;

· Wykład 5: cd: Lemat translacyjny; Twierdzenie Immermana-Szelepcsenyi’ego;

· Wykład 6:Alternujące TMs; ATIME(t) ÍDSPACE(t); NSPACE(t) ÍATIME(t²); ASPACE(t)=DTIME(2^O(t)); Rozpoznawanie słów w#w w ATIME₁(n);

· Wykład 7: Twierdzenie Paula, Pippengera, Szemeredi’ego i Trottera: DTIME(lin)¹NTIME(lin)

· Wykład 8: Kontynuacja wykładu poprzedniego.

· Wykład 9: Klasy probabilistyczne (PP, BPP, ZPP, R). Zamkniętość PP na różnicę symetryczną. Twierdzenie Beigela, Reingolda i Spielmana o zamkniętości PP na przecięcie.

· Wykład 10: Dowody interakcyjne. Twierdzenie Shamira: IP=PSPACE.

· Wykład 11: Zbiory rzadkie. Twierdzenie Bermana o nieistnieniu NP- zupełnych języków nad alfabetem jednoliterowym.

Listy zadań

· Lista 1.

· Lista 2.

· Lista 3.

· Lista 4.

· Lista 5.

· Lista 6.

· Lista 7.

Komunikaty

· Dostępne już są wyniki kolokwium. Osoby, które uzyskały powyżej 25pkt, nie muszą pisać egzaminu w dniu 4.02.2004.

· Początek egzaminu w dniu 4.02.2004: godz. 12.00.