On the Complexity of Restarting

摘要

Restarting is a technique used by many randomized local search and systematic search algorithms. If the algorithm has not been successful for some time, the algorithm is reset and reinitialized with a new random seed. However, for some algorithms and some problem instances, restarts are not beneficial. Luby et al. [12] showed that if restarts are useful, then there is a restart time t* such that the so-called fixed-cutoff strategy is the best possible strategy in expectation. In this work, we show that deciding whether restarts are useful is NP-eomplete. Furthermore, we show that there is no feasible approximation algorithm for the optimal restart time t*. Lastly, we show that calculating the expected runtime for a known probability distribution and a given restart time is #P-complete.