Oppdatering om forelesningene

Jeg er nesten ferdig med å forelese seksjon 8.3 i Sipser. Hele kap. 8 vil bli forelest relativt grundig, men jeg vil ikke si noe om beviset av Teorem 8.5 (Savitchs teorem) og Teorem 8.9 (TQBF er PSAPCE-komplett). Dette er viktige teoremer, men beviset av disse teoremene regnes ikke som pensum. Ellers så vil kjernepensum bestå av kap.7 og kap. 8. I tillegg vi noen utvalgte emner fra kap. 9 regnes som pensum.

Jeg regner med å bruke ca. havparten av neste forelesning på å gjøre meg ferdig med seksjon 8.3. Deretter vil jeg forelse seksjon 8.4, 8.5 og 8.6 i nevnte rekkefølge.