On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

Recoverable robust problems are described by min-max-min formulations. From a complexity-theoretic point of view, such min-max-min problems are often even harder than NP-complete, namely they are often complete for the third stage of the so-called polynomial hierarchy [33]. A problem complete for the $k$-th stage of the hierarchy is called ${\mathrm{\Sigma }}_k^p$-complete. (In this paper, we are concerned mostly with the case of $k=3$). The theoretical study of ${\mathrm{\Sigma }}_k^p$-complete problems is important: If a problem is found to be ${\mathrm{\Sigma }}_3^p$-complete, it means that, under some basic complexity-theoretic assumptions¹¹1More specifically, we assume here that ${\mathrm{\Sigma }}_3^p\ne \text{NP}$. This is a similar assumption to the famous $\text{P}\ne \text{NP}$ assumption, and it is believed to be similarly unlikely. However, the true status of the conjecture is not known. More details can be found in [34]., it is not possible to find an integer programming formulation of the problem of polynomial size [34] (also called a compact model). This means that no matter how cleverly a decision maker tries to design their integer programming model, it must inherently have a huge number of constraints and/or variables, and may be much harder to solve than even NP-complete problems.

Even though this fact makes the study of ${\mathrm{\Sigma }}_3^p$-complete problems compelling, surprisingly few results relevant to the area of min-max-min combinatorial optimization were known until recently. While the usual approach to prove ${\mathrm{\Sigma }}_k^p$-completeness (or NP-completeness) is to formulate a new proof for each single problem, a recent paper by Grüne & Wulf [18], extending earlier ideas by Johannes [26] breaks with this approach. Instead, it is shown that there exists a large ’base list’ of problems (called SSP-NP-complete problems in [18]), including many classic problems like independent set, vertex cover, knapsack, TSP, etc. Grüne and Wulf show that for each problem from the base list, some corresponding min-max version is ${\mathrm{\Sigma }}_2^p$-complete, and some corresponding min-max-min version is ${\mathrm{\Sigma }}_3^p$-complete. This approach has three main advantages: A1.) It uncovers a large number of previously unknown ${\mathrm{\Sigma }}_k^p$-complete problems. A2.) It reveals the theoretically interesting insight, that for all these problems the ${\mathrm{\Sigma }}_k^p$-completeness follows from essentially the same argument. A3.) It can simplify future proofs, since heuristically it seems to be true that for a new problem it is often easier to show that the nominal problem belongs to the list of SSP-NP-complete problems, than to find a ${\mathrm{\Sigma }}_k^p$-completeness proof from scratch.

The main goal of the current paper is to extend the framework of Grüne & Wulf [18] also to the setting of recoverable optimization, since this setting was not considered in the original paper. It turns out that compared to [18] more complicated assumptions are needed. We introduce a set of sufficient conditions for some nominal problem, which imply that the recoverable robust version of that problem is ${\mathrm{\Sigma }}_3^p$-complete.

We consider recoverable robust optimization for the following nominal problems: Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, $p$-center, $p$-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, $k$-directed disjoint path ($k\ge 2$), and Steiner tree. In addition we consider the three most popular distance measures dist used in recoverable robust optimization: The $\kappa$-addition distance, the $\kappa$-deletion distance, and the Hamming distance. (A formal definition of these distance measures is given in Section 4.1)

We show that for every combination of the above problems with any of the three distance measures, the recoverable robust problem (with discrete budgeted uncertainty) is ${\mathrm{\Sigma }}_3^p$-complete. More generally, we identify an abstract property of all our studied problems, and prove that this abstract property already implies that the recoverable robust problem becomes ${\mathrm{\Sigma }}_3^p$-complete. This answers a question asked by Goerigk, Lendl and Wulf [16]. As a consequence, the advantages A1–A3 as explained above also apply to recoverable robust problems. We remark that ${\mathrm{\Sigma }}_3^p$-completeness was already known in the case of clique/independent set, TSP or shortest path combined with the Hamming distance [16]. It was also already known for shortest path in combination with all three distance measures [23] and for several optimization problems [17] for so-called xor-dependencies and $\mathrm{\Gamma }$-set scenarios. Hence our work is an extension of these results.

Let $\mathrm{\Pi }=$ TSP. TSP is encoded as LOP problem the following way: An instance is given by $I=(G,d,t)$, where $G=(V,E)$ is a complete undirected graph, $d:E\to {\mathbb{N}}_0$ are the edge costs and $t$ is the cost threshold. The decision problem of TSP asks if there is a tour $T\subseteq E$ with cost $d(T)\le t$ visiting all vertices from $V$ exactly once. The universe is $𝒰(I)=E$. The set $ℱ(I)\subseteq 2^E$ is the set of all feasible tours (including those of cost greater than $t$). The set $𝒮(I)$ is the set of all tours of cost at most $t$. To turn the TSP into a recoverable robust problem, we “forget” about the cost function $d$ and the threshold $t$. Given $c_1,\underset{¯}{c},\overline{c},\mathrm{\Gamma },\kappa ,t_{\text{RR}}$, the decision problem associated to the recoverable robust TSP (under some fixed distance function $\mathrm{dist}$) is to decide whether Equation 2 holds.

For the proof of the main theorem, we require some definitions. Let $X=\{x_1,\mathrm{\dots },x_n\}$ be a set of binary variables and $L:=\{x_1,\mathrm{\dots },x_n\}\cup \{{\overline{x}}_1,\mathrm{\dots },{\overline{x}}_n\}=X\cup \overline{X}$ be the set of corresponding literals. An assignment is a subset $A\subseteq X\cup \overline{X}$ such that $|A\cap \{x_i,{\overline{x}}_i\}|=1$ for all $i=1,\mathrm{\dots },n$. We say that the assignment $A$ assigns the value $1$ to variable $x_i$, if $x_i\in A$, and $A$ assigns $0$ to $x_i$, if ${\overline{x}}_i\in A$. We remark that this notation for an assignment is non-standard, but it turns out to be convenient in the context of our framework. A Sat-formula $\phi$ is in 3CNF, if it is a conjunction of clauses, and every clause has exactly three literals. We denote by $\phi (A)\in \{0,1\}$ the evaluation of the formula $\phi$ under the assignment $A$. In the following, we often consider the case, where the set of variables is partitioned into three disjoint sets $X,Y,Z$, and denote this case by writing $\phi (X,Y,Z)$.

For the ${\mathrm{\Sigma }}_3^p$-hardness proof, we require a known ${\mathrm{\Sigma }}_3^p$-complete problem to reduce from. It turns out that instead of reducing from the classic problem $\exists \forall \exists$-Satisfiability, it is more convenient to base our proof on Robust Adjustable Sat with budgeted uncertainty (in short, R-Adj-Sat), introduced by Goerigk, Lendl and Wulf [16], which we reformulate to adhere to the notation of this paper:

Problem R-Adj-Sat
Instance: A Sat-formula $\phi (X,Y,Z)$ in 3CNF. A partition of the set of variables into three disjoint parts $X\cup Y\cup Z$ with $|X|=|Y|=|Z|$. An integer $\mathrm{\Gamma }\ge 0$.
Question: Is there an assignment $A_X\subseteq X\cup \overline{X}$ such that for all subsets $Y^{\prime }\subseteq Y$ of size $|Y^{\prime }|\le \mathrm{\Gamma }$, there exist assignments $A_Y\subseteq Y\cup \overline{Y}$ and $A_Z\subseteq Z\cup \overline{Z}$ such that $A_Y\cap Y^{\prime }=\mathrm{\varnothing }$, i.e. set all variables in $Y^{\prime }$ to 0, and $\phi (A_X,A_Y,A_Z)=1$?

The problem R-Adj-Sat is best understood as a game between Alice and Bob: Alice wants to satisfy the formula, Bob wants to achieve the opposite. Alice initially selects an assignment $A_X$ of the variables in $X$. Afterwards, Bob is allowed to select a blocker $Y^{\prime }\subseteq Y$ of size at most $\mathrm{\Gamma }$ and force all these variables to be “0”. Finally, Alice is allowed to assign values to all variables in $Y\cup Z$ that have not yet been assigned. In [16] it is shown that R-Adj-Sat is ${\mathrm{\Sigma }}_3^p$-complete. In order to provide additional insight for the reader, we quickly sketch the main argument in [16]: The idea is to reduce from the classic problem $\exists \forall \exists$-Satisfiability. Let $\exists A_X\forall A_Y\exists A_Z\phi (A_X,A_Y,A_Z)$ be an instance of this problem. How do we transform it into a R-Adj-Sat problem? It is intuitive, that in such a reduction, Alice’s rule of choosing assignments $A_X$ and $A_Z$ should stay roughly the same. However, how do we express the choice of $A_Y$ in terms of a blocker $Y^{\prime }$ that is forced to 0? The idea is to split the variable $y_i\in Y$ into two new variables $y_i^t,y_i^f$ for every $i=1,\mathrm{\dots },n$. We say that Bob plays honestly if for all $i=1,\mathrm{\dots },n$ we have $|\{y_i^t,y_i^f\}\cap Y^{\prime }|=1$. Such an honest choice of $Y^{\prime }$ naturally encodes an assignment $A_Y$. It turns out that, using the pigeonhole principle, and the budget constraint $|Y^{\prime }|\le \mathrm{\Gamma }$, one can enrich the formula $\phi$ with a “cheat-detection-gadget”. This gadget can be used by Alice to win the game trivially if and only if Bob cheats. Hence the modified game of R-Adj-Sat is equivalent to the original instance of $\exists \forall \exists$-Satisfiability.

We prove ${\mathrm{\Sigma }}_3^p$-hardness by providing a reduction from R-Adj-Sat to Comb. RR-$\mathrm{\Pi }$. This reduction will crucially rely on the blow-up SSP reduction from 3Sat to $\mathrm{\Pi }$, which we assumed to exist. More formally, let $\mathrm{\Pi }=({ℐ}_{\mathrm{\Pi }},{𝒰}_{\mathrm{\Pi }},{𝒮}_{\mathrm{\Pi }})$ be an SSP problem, such that there is a blow-up reduction from 3Sat to $\mathrm{\Pi }$ defined by the mappings $g$, ${(f_I)}_{I\in {ℐ}_{\text{Sat}}}$, and blow-up factor ${({\beta }_I)}_{I\in {ℐ}_{\text{Sat}}}$. Recall that by the definition of a blow-up reduction this means the following: Let the term ${ℐ}_{\text{Sat}}$ denote the set of all possible 3Sat instances, i.e. the set of all 3CNF formulas. For each fixed 3Sat instance $I_{\text{Sat}}\in {ℐ}_{\text{Sat}}$, its universe $𝒰(I_{\text{Sat}})$ is the set of positive and negative literals of variables appearing in that formula. By assumption, for every fixed 3Sat instance $I_{\text{Sat}}\in {ℐ}_{\text{Sat}}$ and every set $L_b\subseteq 𝒰(I_{\text{Sat}})$ (with $\mathrm{\ell }\in L_b$ iff $\overline{\mathrm{\ell }}\in L_b$) there exists an equivalent instance $I_{\mathrm{\Pi }}=g(I_{\text{Sat}})$ of $\mathrm{\Pi }$. Furthermore, associated to each fixed 3Sat instance $I_{\text{Sat}}\in {ℐ}_{\text{Sat}}$ we have a function $f_{I_{\text{Sat}}}$, which describes in which way the universe of $I_{\text{Sat}}$ can be injectively embedded into the universe of the equivalent instance $I_{\mathrm{\Pi }}$ such that the SSP property is true. Finally, there is a tight correspondence between solutions of $I_{\mathrm{\Pi }}$ having distance at most ${\beta }_{I_{\text{Sat}}}$, and (the pre-image of) the solutions agreeing on the set $L_b$. For brevity of notation, in the following we often write $𝒰(I_{\mathrm{\Pi }})$ instead of ${𝒰}_{\mathrm{\Pi }}(I_{\mathrm{\Pi }})$ and $𝒮(I_{\mathrm{\Pi }})$ instead of ${𝒮}_{\mathrm{\Pi }}(I_{\mathrm{\Pi }})$ to denote the solution set/universe associated to instance $I_{\mathrm{\Pi }}$, if the correct subscript is clear from the context.

We now turn our attention to the ${\mathrm{\Sigma }}_3^p$-hardness proof. As explained above, the problem R-Adj-Sat is ${\mathrm{\Sigma }}_3^p$-complete. Let an R-Adj-Sat instance $I_{\text{RAS}}$ be given. Our goal is to transform this instance into a new instance $I_{\text{RR}\mathrm{\Pi }}$ of Comb. RR-$\mathrm{\Pi }$ such that

Clearly if we can achieve this goal we are done. By definition of the problem R-Adj-Sat, the instance $I_{\text{RAS}}$ consists of the following parts:

where $\phi \in {ℐ}_{\text{Sat}}$ is a 3CNF-formula, whose variables are partitioned into three parts $X,Y,Z$ of equal size $n:=|X|=|Y|=|Z|$, and $\mathrm{\Gamma }\in {\mathbb{N}}_0$. Let the corresponding literal sets $X,Y,Z$ be denoted by $L_X:=X\cup \overline{X}$, $L_Y:=Y\cup \overline{Y},$ and $L_Z:=Z\cup \overline{Z}$. Note that the universe associated to the 3Sat-instance $\phi$ is $L_X\cup L_Y\cup L_Z$. Let us denote this fact by writing $𝒰(\phi )=L_X\cup L_Y\cup L_Z$.

Given the instance $I_{\text{RAS}}$ as input, we describe in the following how to construct the instance $I_{\text{RR}\mathrm{\Pi }}$ of Comb. RR-$\mathrm{\Pi }$, which consists of the following parts:

Here, $I_{\mathrm{\Pi }}$ is an instance of the nominal problem $\mathrm{\Pi }$, $B\subseteq 𝒰(I_{\mathrm{\Pi }})$ is the set of blockable elements, ${\mathrm{\Gamma }}^{\prime }\in {\mathbb{N}}_0$ is the uncertainty budget, and $\kappa \in {\mathbb{N}}_0$ is the recoverability parameter.

Before we give a formal description of $I_{\mathrm{\Pi }},B,{\mathrm{\Gamma }}^{\prime },$ and $\kappa$, we explain the rough idea: In particular, what is the right choice for the instance $I_{\mathrm{\Pi }}$? The answer is provided by the blow-up reduction. Note that this reduction can take in any 3CNF formula and a subset $L_b$ of the literals (with the property that $\mathrm{\ell }\in L_b$ iff $\overline{\mathrm{\ell }}\in L_b$ for all literals $\mathrm{\ell }$) and produce an instance $I$ of $\mathrm{\Pi }$. Note that the set $L_b$ gets “blown up” by the reduction. We claim that $L_b=L_X$ is a good choice. Indeed, consider the following formal definition of $I_{\text{RR}\mathrm{\Pi }}$.

Description of the Instance $I_{\text{RR}\mathrm{\Pi }}$.

Let $g$, ${(f_{\phi })}_{\phi \in {ℐ}_{\text{Sat}}}$, and ${({\beta }_{\phi })}_{\phi \in {ℐ}_{\text{Sat}}}$ be the objects describing the blow-up reduction from 3Sat to $\mathrm{\Pi }$ for the fixed choice of $L_b:=L_X$. We let $I_{\mathrm{\Pi }}=g(\phi )$ be the instance produced by the blow-up reduction applied to the formula $\phi$ and the literal set $L_b=L_X$. We remark that the following holds by the definition of the blow-up reduction: A blow-up reduction in particular is also an SSP reduction. Hence the function $f_{\phi }:𝒰(\phi )\to 𝒰(I_{\mathrm{\Pi }})$ maps the literals of $\phi$ injectively to elements of the new universe $𝒰(I_{\mathrm{\Pi }})$. We can hence define the set of blockable elements

$$B:=f_{\phi }(Y),$$

where $Y\subseteq 𝒰(\phi )$ describes the positive literals in $L_Y$ (recall that $L_Y=Y\cup \overline{Y}$).

Furthermore, note that by definition of a blow-up reduction, there exists some ${\beta }_{\phi }\in \mathbb{N}$, computable in poly-time, with the property that for all $S_1,S_2\in 𝒮(I_{\mathrm{\Pi }})$:

$$\mathrm{dist}(S_1,S_2)\le {\beta }_{\phi }\iff S_1\cap f_{\phi }(L_X)=S_2\cap f_{\phi }(L_X).$$

In other words, the new instance $I_{\mathrm{\Pi }}$ has the property that two solutions of it have small distance if and only if they agree on $f_{\phi }(L_X)$, i.e. they agree on those universe elements of $𝒰(I_{\mathrm{\Pi }})$ that correspond to $L_X$. We finally define

$$\kappa :={\beta }_{\phi }\text{ and }{\mathrm{\Gamma }}^{\prime }:=\mathrm{\Gamma }.$$

This completes the description of the instance $I_{\text{RR}\mathrm{\Pi }}=(I,B,{\mathrm{\Gamma }}^{\prime },\kappa )$.

Correctness

We start the correctness proof by showing

$I_{\text{RAS}}\text{is a Yes-instance}\Rightarrow I_{\text{RR}\mathrm{\Pi }}=(I_{\mathrm{\Pi }},B,\mathrm{\Gamma },\kappa )\text{is a Yes-instance}.$

In this case, let $A_X\subseteq X\cup \overline{X}$ be an assignment of the variables $X$ with the property that

$$\forall Y^{\prime }\subseteq Y,|Y^{\prime }|\le \mathrm{\Gamma }:\exists A_Y,A_Z:A_Y\cap Y^{\prime }=\mathrm{\varnothing }\text{ and }\phi (A_X,A_Y,A_Z)=1.$$

Such an $A_X$ exists by assumption that $I_{\text{RAS}}$ is a Yes-instance. Now, let $Y^{\prime }\subseteq Y$ be an arbitrary subset of $Y$ with $|Y^{\prime }|\le \mathrm{\Gamma }$. Then, it is possible to choose assignments $A_Y,A_Z$ of $Y,Z$ such that $A_Y\cap Y=\mathrm{\varnothing }$ and $\phi (A_X,A_Y,A_Z)=1$. We consider such an assignment $A_1:=A_X\cup A_Y\cup A_Z$. Note that if we interpret $\phi$ as 3Sat instance, $A_1\subseteq 𝒰(\phi )$ and even $A_1\in 𝒮(\phi )$, due to $\phi (A_1)=1$. Since the blow-up reduction is in particular an SSP reduction, we can make use of the central property of SSP reductions. The property implies that the 3Sat solution $A_1$ can be “lifted” to a solution of $\mathrm{\Pi }$. More precisely, there exists a solution $S_1\in 𝒮(I_{\mathrm{\Pi }})$, such that

$$S_1\cap f_{\phi }(𝒰(\phi ))=f_{\phi }(A_1).$$

(Intuitively, the solution $S_1\in 𝒮(I_{\mathrm{\Pi }})$ of the nominal problem instance $I_{\mathrm{\Pi }}$ corresponds to the solution $A_1\in 𝒮(\phi )$ of the 3Sat instance $\phi$ when restricted to the injective embedded “sub-instance” of 3Sat inside $\mathrm{\Pi }$.)

We claim that $S_1$ is a solution for $I_{\text{RR}\mathrm{\Pi }}$. To prove this claim we have to show that for all blockers $B^{\prime }\subseteq B$ with $|B^{\prime }|\le {\mathrm{\Gamma }}^{\prime }=\mathrm{\Gamma }$, there exists a solution $S_2\in 𝒮(I_{\mathrm{\Pi }})$ with $S_2\cap B^{\prime }=\mathrm{\varnothing }$ and $\mathrm{dist}(S_1,S_2)\le \kappa$. Indeed, such a solution $S_2$ exists for all choices of blockers $B^{\prime }$. This can be seen by applying the following construction: Repeat exactly the same construction as for $S_1$, except that the set $Y^{\prime }$ is not chosen arbitrarily. Instead, choose $Y^{\prime }$ by letting $Y^{\prime }:=f_{\phi }^{-1}(B^{\prime })$. Note that by the definition of $B$, the set $Y^{\prime }$ is well-defined, i.e. $Y^{\prime }\subseteq Y$, $|Y^{\prime }|\le \mathrm{\Gamma }$, and $f_{\phi }(Y^{\prime })=B^{\prime }$. Repeating the same construction, assignment $A_X$ stays the same, but we obtain different assignments $A_Y^{\prime },A_Z^{\prime }$ with $A_Y^{\prime }\cap Y^{\prime }=\mathrm{\varnothing }$ and $\phi (A_X,A_Y^{\prime },A_Z^{\prime })=1$. We let $A_2:=A_X\cup A_Y^{\prime }\cup A_Z^{\prime }$. Again, by the SSP property there exists a solution $S_2\in 𝒮(I_{\mathrm{\Pi }})$ such that $S_2\cap f_{\phi }(𝒰(\phi ))=f_{\phi }(A_2)$. Therefore we have

$$\mathrm{\varnothing }=A_2\cap Y^{\prime }=f_{\phi }(A_2)\cap f_{\phi }(Y^{\prime })=(S_2\cap f_{\phi }(𝒰(\phi )))\cap B^{\prime }=S_2\cap B^{\prime }.$$

Note that $A_X$ is the same in both constructions. Therefore $S_1\cap f_{\phi }(L_X)=S_2\cap f_{\phi }(L_X)$, and hence by the definition of a blow-up reduction, we have $\mathrm{dist}(S_1,S_2)\le {\beta }_{\phi }=\kappa$. In total, we have shown that $S_1$ is a solution of $\mathrm{\Pi }$ such that for every blocker $B^{\prime }\subseteq B$, with $|B^{\prime }|\le \mathrm{\Gamma }$, there exists a good solution $S_2$. This shows that $I_{\text{RR}\mathrm{\Pi }}$ is yes-instance.

It remains to consider the reverse direction:

$I_{\text{RR}\mathrm{\Pi }}=(I,B,{\mathrm{\Gamma }}^{\prime },\kappa )\text{ is a Yes-instance}\Rightarrow I_{\text{RAS}}\text{ is a Yes-instance}$

The strategy is very similar, with the difference that we use the SSP property and the blow-up property in the reverse direction. Consider some solution $S_1\in 𝒮(I_{\mathrm{\Pi }})$ which satisfies

$$\forall B^{\prime }\subseteq B,|B^{\prime }|\le {\mathrm{\Gamma }}^{\prime }:\exists S_2\in 𝒮(I_{\mathrm{\Pi }}),S_2\cap B^{\prime }=\mathrm{\varnothing }:\mathrm{dist}(S_1,S_2)\le \kappa .$$

We have to show that there exists an assignment $A_X\subseteq X\cup \overline{X}$ such that for all subsets $Y^{\prime }\subseteq Y$ there are assignments $A_Y,A_Z$ with $A_Y\cap Y=\mathrm{\varnothing }$ and $\phi (A_X,A_Y,A_Z)=1$. Indeed, to define $A_X$, consider solution $S_1$. By the SSP property, since $S_1\in 𝒮(I_{\mathrm{\Pi }})$, the set $f_{\phi }^{-1}(S_1)\subseteq 𝒰(\phi )$ is a set of literals which satisfies $\phi$. We let $A_X$ be the restriction of that satisfying assignment to the variables in $X$. More formally, we let $A_X:=f_{\phi }^{-1}(S_1)\cap L_X$.

We claim that this assignment $A_X$ proves that $I_{\text{RAS}}$ is a yes-instance. Indeed, let some set $Y^{\prime }\subseteq Y$, with $|Y^{\prime }|\le \mathrm{\Gamma }$, be given. We define the blocker to be $B^{\prime }:=f_{\phi }(Y^{\prime })$. Observe that $B^{\prime }\subseteq f_{\phi }(Y)=B$, and $|B^{\prime }|\le \mathrm{\Gamma }$. Therefore there exists $S_2\in 𝒮(I)$ such that $S_2\cap B^{\prime }=\mathrm{\varnothing }$ and $\mathrm{dist}(S_1,S_2)\le \kappa$. We can again interpret the solution $S_2$ as an assignment $A_2:=f_{\phi }^{-1}(S_2)$. By the SSP property, this assignment satisfies $\phi$, that is $A_2\in 𝒮(\phi )$. Since $\mathrm{dist}(S_1,S_2)\le \kappa ={\beta }_{\phi }$, we have $S_1\cap f_{\phi }(L_X)=S_2\cap f_{\phi }(L_X)$ by the property of a blow-up reduction. This in turn implies $A_2\cap (X\cup \overline{X})=A_X$. Finally, we have $\mathrm{\varnothing }=S_2\cap B^{\prime }=f_{\phi }^{-1}(S_2)\cap f_{\phi }^{-1}(B^{\prime })=A_2\cap Y^{\prime }$. This shows that $I_{\text{RAS}}$ is a yes-instance, and concludes the proof.

Polynomial Time.

The instance $I_{\text{RR}\mathrm{\Pi }}=(I_{\mathrm{\Pi }},B,{\mathrm{\Gamma }}^{\prime },\kappa )$ can indeed be constructed in polynomial time. The nominal instance $I_{\mathrm{\Pi }}$ can be computed polynomially, since the map $g$ in the SSP reduction can be computed polynomially. The set $B$ can be computed polynomially, since the map $f_{\phi }$ in the SSP reduction can be computed polynomially. The number $\kappa ={\beta }_{\phi }$ can be computed polynomially by definition of a blow-up SSP reduction. The number $\mathrm{\Gamma }$ remains the same.

$◀$

We have shown that the combinatorial version is indeed ${\mathrm{\Sigma }}_3^p$-hard as long as the nominal SSP problem $\mathrm{\Pi }$ is SSP-NP-hard with a blow-up SSP reduction from Satisifiability. This however does not directly imply that the linear optimization version RR-$\mathrm{\Pi }$ is also ${\mathrm{\Sigma }}_3^p$-hard. We remedy this problem with a short reduction that simulates the set of blockable elements in Comb. RR-$\mathrm{\Pi }$ with the cost functions in RR-$\mathrm{\Pi }$ that results in the following theorem.