PREMESSA:

Bisogna conoscere tutte le definizioni formali e tutti gli enunciati dei teoremi.

A volte il libro contiene piu' dettagli, a volte se ne trovano di piu' nelle slides. Bisogna conoscere l'unione di tutti i dettagli.

Mi aspetto che siano conosciute tutte le dimostrazioni banali, anche se non indicate qui sotto (ad es. il contenimento di una classe deterministica nella corrispondente classe nondeterministica, la Prop. 2.1, la chiusura delle classi deterministiche rispetto al complemento, ecc.)

DIMOSTRAZIONI DA CONOSCERE ASSOLUTAMENTE 

[lezione-2.pdf]
Teorema dello speedup multinastro

[lezione-3.pdf]
Dimostrazione che NTIME(f(n) e' contenuta in TIME(k^f(n))  [slide #27 e segg.]

[lezione-4.pdf]
Terminazione delle MdT space-bounded  [slide #12 e segg.]

[lezione-5.pdf]
Teorema di Savitch e i suoi 2 corollari [slide #47 e segg.]

[lezione-6.pdf]
Proposizione 8.4
Teorema di Cook (NP-completezza di SAT)

[lezione-7]
Prop. 9.1 [slide #8 e segg.]

[lezione-8]
Proposizioni A-D, [slide #7 e segg.]

[lezione-9]
Teorema 17.11 + Corollario, #82, #85

[lezione-10]
Proposizione su relazioni tra FSAT e SAT, [slides #11-12]
Thm 10.2, [slide #13]

[lezione-Q]
Le due Proposizioni nella slide #20

[lezione-X]
Teorema 20.1 [slides #6 e segg.]