32 Grüne, Christoph Manfred Rossmanith, Peter Goerigk, Marc 121110 121220 080060 RWTH Aachen University Aachen English 1 Online-Ressource : Illustrationen This thesis deals with the complexity of robust, bilevel, and online optimization. In these areas, we are concerned with min-max (respectively multi-stage) problems from the popular areas of network interdiction, most vital vertex problems, min-max regret optimization, two-stage adjustable problems, recoverable robustness, and online optimization. Although these areas have been well-researched for more than two decades, and one would naturally expect most of the problems to be complete for lower levels of the polynomial hierarchy or polynomial space, almost no hardness results are known. We address this issue by designing two reduction frameworks with the goal of analyzing the common substructure of combinatorial problems that include some form of uncertainty, which induces similar complexity behavior. The reduction frameworks work as follows. We first provide a general definition of a combinatorial problem, which is also called the nominal problem. Based on this definition of a nominal problem, we are able to derive definitions for more general variations of that problem that additionally model some kind of uncertainty. The general idea is now to examine the reductions between the nominal problems and determine if additional properties hold that help us to directly derive reductions for the more general variations. Accordingly, we provide a definition of such a reduction and show that these properties are already fulfilled by existing reductions or slight modifications of them. We apply these frameworks to nominal problems that are $\mathsf{NP}$-complete and derive complexity results for completeness in the polynomial hierarchy and in $\mathsf{PSPACE}$.The first framework is concerned with subset search problems (or in short SSP), thus it is named SSP framework. A subset search problem is a combinatorial problem that consists of instances $\mathcal{I}$ that contain a universe $\mathcal{U}$ together with additional information. A solution $S \in \mathcal{S}$ is a subset of the universe, i.e. $S \subseteq \mathcal{U}$.The corresponding SSP reductions are usual reductions with an additional injective function that maps the universe of the one problem into that of the other. Indeed, many existing reductions on the $\mathsf{NP}$-level fulfill this SSP property. Based on this notion, we are able to "upgrade" the SSP reductions between the nominal problems to reductions between the problem versions in the areas of robust and bilevel optimization. Concretely, we apply this framework to the areas of interdiction, min-max regret optimization, two-stage adjustable robustness, and recoverable robustness, and prove $\Sigma^p_2$- and $\Sigma^p_3$-completeness for the corresponding problems if the nominal problem is $\mathsf{NP}$-complete. The second framework considers combinatorial problems, which can be described by an underlying universe $U$ and nested relations $R$ over the universe. The corresponding reduction is termed universe gadget reduction. The special property of a universe gadget reduction from problem $A$ to $B$ is that a gadget is created for every universe element and every relational element from any of the relations of problem $A$. These gadgets consist of the universe and relation elements of the problem $B$ and are disjoint. Based on this reduction, we are able to show $\Sigma^p_3$-completeness for variations of recoverable robust problems and $\mathsf{PSPACE}$-completeness for several online graph problems with a map. Veröffentlicht auf dem Publikationsserver der RWTH Aachen University ; Dissertation, RWTH Aachen University, 2025 ; 2, ; PUB:(DE-HGF)11, ; Dissertation / PhD Thesis Dissertation RWTH Aachen University 2025 2025 RWTH-2025-09741 2025 https://publications.rwth-aachen.de/record/1021909