Следствие теоремы Савича: NPSPACE=PSPACE. Вероятностный алгоритм достижимости в неориентированном графе, использующий $ O(\log n) $ памяти. Вычисление достижимости в графе схемой полиномиального размера и глубины $ O(\log^2 n) $. Параллельное вычисление функций, вычислимых с использованием $ O(\log n) $ памяти.