Rapport fra forelesningene
På de to siste forelesningene har jeg snakket om
-
de fiinisjonen av PSPACE
-
de finisjonen av PSPACE-komplett problem
-
hvor mye tid en turingmaskin som arbeider i rom f(n) kan bruke.
Videre, så har jeg snakket om de PSPACE-komplette problemene TQBF, FG (Formula Game) og GG (Geography Game). Vi har sett hvordan FG kan reduseres til GG i polynom tid. Vi har også sett på Savitchs teorem. Det er viktig teorem, men vi har ikke gått gjennom beviset på forelesningene.
På tirsdag begynner jeg å forelese seksjon 8.4 i Sipsers bok (om N og NL).
Publisert 19. apr. 2015 23:53