Lezione 34 - 15 Maggio 2020
Schema della sezione
-
La lezione è stata trasmessa in streaming su Microsoft Teams il 15 maggio 2020. La registrazione dello stream è disponibile su https://web.microsoftstream.com/video/b91ab394-bfff-425b-8f43-5c5d51767b73
Nel caso si voglia approfondire l'argomento del Teorema di Savitch, l'articolo originale è "Relationships between nondeterministic and deterministic tape complexities" disponibile su https://www.sciencedirect.com/science/article/pii/S002200007080006X. Una dimostrazione per il caso di spazio f(n)≥n è disponibile sul libro "Introduction to the Theory of Computation", 3rd edition di Michael Sipser alle pagine 333-335 (capitolo 8, sezione 8.1).