Controlling a Random Population: complexity

The population control problem asks whether an arbitrarily large population of finite state machines can be successfully controlled using a discrete time control where at every step, the chosen action is uniformly applied to all machines. The goal of the controller is to eventually put all machines in a final state. This is typically what happens if you organize a conference and have to chose every day a unique program for the whole audience which is interesting enough so that all participants to attend all talks. The larger the audience, the harder it is. The case where the machines are non-deterministic is called the population control problem. It has been tackled by Bertrand et al. in https: //arxiv. org/abs/1807. 00893. The case where the machines are MDPs is called the random population control problem. It has been shown decidable by Colcombet et al. in https: //arxiv. org/abs/1911. 01195 using Dickson's Lemma, the min-cut max-flow duality and distance automata. The exact complexity is still opened. A lower bound is EXPTIME, as shown by Mascle at al. https: //arxiv. org/abs/1909. 06420. We show that Corto's conjecture about the random case: an arbitrarily large random population can be controlled using solely 0, 1, \omega's and small quadratic constants. This almost-surely closes the complexity gap.

Authors

• Hugo Gimbert

Keywords

No keywords are indexed for this paper.