Estimation of the characteristics of time-memory-data tradeoff methods via generating functions of the number of particles and the total number of particles in the Galton–Watson process

Алгоритмы балансировки времени-памяти-данных используются для обращения однонаправленных функций. В работе приводятся математические результаты, позволяющие провести точный анализ сложности большинства известных алгоритмов такого типа. Для вероятностной модели получены оценки средних значений некоторых характеристик с помощью исследования предельного поведения производящих функций совместных распределений числа частиц и общего числа частиц в докритических и критических процессахъ Гальтона–Ватсона.