Точный баланс между объемом памяти и шумом при вычислении эргодических мер

Установлена точная оценка на сложность (по памяти) вычисления эргодической меры динамической системы малой размерности с дискретным временем, испытывающей влияние гауссовского шума. Если величина шума равна $\varepsilon$, а функция, описывающая эволюцию системы, не представляет трудностей с точки зрения вычислительной сложности, то функция плотности эргодической меры может быть приближена с точностью $\delta$ с использованием памяти, полиномиальной от $\log 1/\varepsilon+\log\log 1/\delta$. Также показано, что эта оценка точна с точностью до полиномиального множителя.
В процессе доказательства вышеназванного факта установлен представляющий независимый интерес факт о вычислениях с ограниченной памятью: матрицу размера $n\times n$ возможно возвести в экспоненциально большую степень с использованием памяти, полилогарифмической по $n$.
Библиография: 25 названий.