Podstawy obliczeń na TMs (Redukcja taśm dla (D,N.A) TM, Speed-up, etc.)
Podstawowe relacje między klasami obliczeń (hierarchia czasowa/ pamięciowa; obliczenia det/net/alt
Diagonalizacja
Lemat translacyjny
Hierarchia wielomianowa
Dolne ograniczenie na pamięć na rozpoznawanie języków nieregularnych
Twierdzenie (Immelman, Szelepcsenyi) Zamkniętość NSPACE na dopełnienie
Twierdzenie (Mahaney): Konsekwencja istnienia NP-zupełnego zbioru rzadkiego
Twierdzenie (Hopcroft, Paul, Valiant): DTIME(t) \subseteq DSPACE(t/log t)
Twierdzenie (Weigel): Zamkniętość PP na przecięcie
Twierdzenie (Valiant): Permanent jest \#P zupełny
Twierdzenie (Paul, Pippenger, Szemeredi, Trotter): DTIME(n) \subset NTIME(n)
Twierdzenie (Toda) PH \subseteq P^{\#SAT}
Twierdzenie (Shamir): IP = PSPACE
Podstawy PCP