Die zweite Ebene der Polynomhierarchie enthält eine Vielzahl von Optimierungsproblemen, die auf natürliche Weise mit einem existentiellen und einem universellen Quantifizierer formuliert werden können. Ein typisches Beispiel in der robusten Optimierung wäre die Frage, ob es einen Produktionsplan gibt, der unter ALLEN möglichen Preisszenarien für Strom in den kommenden zwei Jahren einigermaßen gut abschneidet. In ähnlicher Weise würde ein typisches Problem in der zweistufigen Optimierung die Frage stellen, ob es eine Möglichkeit gibt, die Steuern so festzulegen, dass ALLE optimalen Verhaltensweisen der Bürger zu angemessenen Steuereinnahmen führen.

Probleme dieser Art sind aus der Sicht der mathematischen Optimierung besonders schwierig zu lösen und erfordern fortgeschrittene Werkzeuge, die auf Zerlegungsalgorithmen, konvexer Optimierung und kombinatorischer Optimierung basieren. Aus Sicht der Komplexitätstheorie sind viele dieser Probleme für die Klasse Σ2p vollständig und höchstwahrscheinlich nicht in der Klasse NP enthalten. Aus diesem Grund sind die Methoden, die in den letzten 50 Jahren für NP-komplette Probleme entwickelt wurden, nicht direkt auf robuste und/oder zweistufige Optimierungsprobleme anwendbar.

Während es bei rein konvexen Problemen einige Fortschritte gegeben hat, sind ganzzahlige Rückgriffsprobleme (robuste Optimierung) und ganzzahlige Folgeprobleme (bilevel Optimierung) noch immer schlecht verstanden, was dazu führt, dass neue Techniken, Tricks, Erkenntnisse und Algorithmen entwickelt werden müssen, um diese Probleme besser in den Griff zu bekommen.