Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.12350
curl -X POST /api/v1/records/arxiv/2602.12350/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.12350/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'