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