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