On the Complexity of Robust Multi-Stage Problems in the Polynomial Hierarchy

We study the computational complexity of multi-stage robust optimization problems. Such multi-stage problems are formulated with alternating min/max quantifiers and therefore naturally fall into higher stage of the polynomial hierarchy. Despite this, almost no hardness result with respect to the polynomial hierarchy are known for robust multi-stage problems. In this work, we examine the hardness of robust two-stage adjustable and robust recoverable optimization with budgeted uncertainty sets. Our main technical contribution is the introduction of a technique tailored to prove $\Sigma^p_3$-hardness of such problems. We highlight a difference between continuous and discrete budgeted uncertainty: In the discrete case, indeed a wide range of problems becomes complete for the third stage of the polynomial hierarchy. We highlight the TSP, independent set, and vertex cover problems as examples of this behavior. However, in the continuous case this does not happen and all problems remain in the first stage of the hierarchy. Finally, if we allow the uncertainty to not only affect the objective, but also multiple constraints, then this distinction disappears and even in the continuous case we encounter hardness for the third stage of the hierarchy. This shows that even robust problems which are already NP-complete can still exhibit a significant computational difference between column-wise and row-wise uncertainty.