HSE, theory of computation, lecture 6: space complexity

-- (directed) reachability is in SPACE(log^2 n) -- PSPSACE = NPSPACE (Savitch'es theorem briefly) -- TQBF is PSPACE-complete -- Generalized geography is PSPACE-complete Course website: http://wiki.cs.hse.ru/Theory_of_computation_2025