A direct application of the rotor-routing automaton is that several structural properties of Markov chains can be approximated or bounded by rotor walks see [1]}, [2]}, [3]}. It seems natural to extend these results to decisional variants and define rotor analogs for Markov decision processes and stochastic games [4]}. It is proved in [4]} that deciding if a player can ensure some value is NP-complete for the one-player version and PSPACE-complete for the two-player version.

Прямое применение автомата роторной маршрутизации заключается в том, что несколько структурных свойств цепей Маркова могут быть аппроксимированы или ограничены с помощью роторных прогулок (см. [1], [2], [3]). Кажется естественным расширить эти результаты на задачи принятия решений и определить роторные аналоги для процессов принятия решений Маркова и стохастических игр (см. [4]). В [4] доказано, что решение задачи о том, может ли игрок гарантировать определенное значение, является NP-полной для версии с одним игроком и PSPACE-полной для версии с двумя игроками.