Эта публикация цитируется в
2 статьях
Точный баланс между объемом памяти и шумом при вычислении эргодических мер
М. Браверманa,
К. Рохасb,
Дж. Шнайдерa a Princeton University, Princeton, NJ, USA
b Universidad Andrés Bello, Santiago, Chile
Аннотация:
Установлена точная оценка на сложность (по памяти) вычисления эргодической меры динамической системы малой размерности с дискретным временем, испытывающей влияние гауссовского шума. Если величина шума равна
$\varepsilon$, а функция, описывающая эволюцию системы, не представляет трудностей с точки зрения вычислительной сложности, то функция плотности эргодической меры может быть приближена с точностью
$\delta$ с использованием памяти, полиномиальной от
$\log 1/\varepsilon+\log\log 1/\delta$. Также показано, что эта оценка точна с точностью до полиномиального множителя.
В процессе доказательства вышеназванного факта установлен представляющий независимый интерес факт о вычислениях с ограниченной памятью: матрицу размера
$n\times n$ возможно возвести в экспоненциально большую степень с использованием памяти, полилогарифмической по
$n$.
Библиография: 25 названий.
Ключевые слова:
динамические системы, вычисления с ограниченной памятью.
УДК:
517.938+
510.581
MSC: Primary
68Q05,
37C40; Secondary
03D15 Поступила в редакцию: 15.12.2016 и 15.05.2017
DOI:
10.4213/sm8884