In bilevel and robust optimization we are concerned with combinatorial min-max problems, for example from the areas of min-max regret robust optimization, network interdiction, most vital vertex problems, blocker problems, and two-stage adjustable robust optimization. Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the classes $Σ^p_2$ or $Σ^p_3$ from the polynomial hierarchy, almost no hardness results in this regime are currently known. However, such complexity insights are important, since they imply that no polynomial-sized integer program for these min-max problems exist, and hence conventional IP-based approaches fail. We address this lack of knowledge by introducing over 70 new $Σ^p_2$-complete and $Σ^p_3$-complete problems. The majority of all earlier publications on $Σ^p_2$- and $Σ^p_3$-completeness in said areas are special cases of our meta-theorem. Precisely, we introduce a large list of problems for which the meta-theorem is applicable (including clique, vertex cover, knapsack, TSP, facility location and many more). We show that for every single of these problems, the corresponding min-max (i.e. interdiction/regret) variant is $Σ^p_2$- and the min-max-min (i.e. two-stage) variant is $Σ^p_3$-complete.

翻译：在双层与鲁棒优化中，我们关注组合最小-最大问题，例如来自最小-最大遗憾鲁棒优化、网络阻断、最关键顶点问题、阻塞器问题以及两阶段可调鲁棒优化等领域。尽管这些领域已被深入研究超过二十年，人们自然会预期这些领域中出现的许多（若非大多数）问题对于多项式层级中的 $Σ^p_2$ 或 $Σ^p_3$ 类具有完备性，但目前几乎未有此类复杂性结果被揭示。然而，此类复杂性洞见至关重要，因为它们意味着这些最小-最大问题不存在多项式规模的整数规划，从而导致传统的基于整数规划的方法失效。我们通过引入超过 70 个新的 $Σ^p_2$-完备和 $Σ^p_3$-完备问题来填补这一知识空白。上述领域中早期关于 $Σ^p_2$- 和 $Σ^p_3$-完备性的绝大多数文献均是我们元定理的特例。具体而言，我们列出了一系列适用于元定理的问题（包括团、顶点覆盖、背包问题、旅行商问题、设施选址等众多问题）。我们证明，对于其中每一个问题，其对应的最小-最大（即阻断/遗憾）变体是 $Σ^p_2$-完备的，而最小-最大-最小（即两阶段）变体是 $Σ^p_3$-完备的。