  Because $\Sigma^p_2$- and $\Sigma^p_3$-hardness proofs are usually tedious
and difficult, not so many complete problems for these classes are known. This
is especially true in the areas of min-max regret robust optimization, network
interdiction, most vital vertex problems, blocker problems, and two-stage
adjustable robust optimization problems. 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 above
classes, almost no completeness results exist in the literature. We address
this lack of knowledge by introducing over 70 new $\Sigma^p_2$-complete and
$\Sigma^p_3$-complete problems. We achieve this result by proving a new
meta-theorem, which shows $\Sigma^p_2$- and $\Sigma^p_3$-completeness
simultaneously for a huge class of problems. The majority of all earlier
publications on $\Sigma^p_2$- and $\Sigma^p_3$-completeness in said areas are
special cases of our meta-theorem. Our precise result is the following: 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). For every problem on this list, we show: The interdiction/minimum cost
blocker/most vital nodes problem (with element costs) is $\Sigma^p_2$-complete.
The min-max-regret problem with interval uncertainty is $\Sigma^p_2$-complete.
The two-stage adjustable robust optimization problem with discrete budgeted
uncertainty is $\Sigma^p_3$-complete. In summary, our work reveals the
interesting insight that a large amount of NP-complete problems have the
property that their min-max versions are 'automatically' $\Sigma^p_2$-complete.
