The complexity of optimal queuing network control

We show that several well-known optimization problems related to the optima l control of queues are provably intractable-independently of any unproven conjecture such as P not equal NP. In particular, we show that several vers ions of the problem of optimally controlling a simple network of queues wit h simple arrival and service distributions and multiple customer classes is complete for exponential time. This is perhaps the first such intractabili ty result for a well-known optimization problem. We also show that the rest less bandit problem (the generalization of the multi-armed bandit problem t o the case in which the unselected processes are not quiescent) is complete for polynomial space.