论文标题
关于多项式层次结构中强大的多阶段问题的复杂性
On the Complexity of Robust Multi-Stage Problems in the Polynomial Hierarchy
论文作者
论文摘要
我们研究了多阶段可靠优化问题的计算复杂性。此类问题是通过交替的最小/最大量词来提出的，因此自然落入了多项式层次结构的较高阶段。尽管如此，关于多项式层次结构的几乎没有硬度结果。 在这项工作中，我们研究了预算不确定性集的可稳定性两阶段可调节且可重新恢复的优化的硬度。我们的主要技术贡献是引入一种量身定制的技术，该技术证明了这些问题的$σ^p_3 $ - hardness。我们强调了连续和离散预算的不确定性之间的区别：在离散的情况下，在多项式层次结构的第三阶段中，多种问题变得完整。特别是，这适用于TSP，独立集和顶点覆盖问题。但是，在连续的情况下，这并没有发生，并且问题仍然存在于层次结构的第一阶段。最后，如果我们允许不确定性不仅影响目标，而且影响多个约束，那么这种区别就会消失，即使在连续的情况下，我们也会遇到层次结构第三阶段的硬度。这表明，即使已经是NP完整的鲁棒问题，仍然可以在列的不确定性和行之间表现出显着的计算差异。
We study the computational complexity of multi-stage robust optimization problems. Such problems are formulated with alternating min/max quantifiers and therefore naturally fall into a higher stage of the polynomial hierarchy. Despite this, almost no hardness results with respect to the polynomial hierarchy are known. 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 $Σ^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; in particular, this applies to the TSP, independent set, and vertex cover problems. However, in the continuous case this does not happen and 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.
