Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912901836570624 |
|---|---|
| author | Grüne, Christoph Johannes, Berit Orlin, James B. Wulf, Lasse |
| author_facet | Grüne, Christoph Johannes, Berit Orlin, James B. Wulf, Lasse |
| contents | Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete.
Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12350 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP Grüne, Christoph Johannes, Berit Orlin, James B. Wulf, Lasse Computational Complexity Combinatorics Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete. Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems. |
| title | Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2602.12350 |