Complexity of Unambiguous Problems in $Σ^P_2$
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911559129759744 |
|---|---|
| author | Gilboa, Matan Goldberg, Paul W. Koutsoupias, Elias Nisan, Noam |
| author_facet | Gilboa, Matan Goldberg, Paul W. Koutsoupias, Elias Nisan, Noam |
| contents | Various practical problems within the class $Σ_{2}^P$ possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing all unambiguous $Σ_{2}^P$ problems is denoted $UΣ_{2}^P$. Examples include the existence of (1) a dominating strategy in a game, (2) a Condorcet winner, (3) a strongly popular partition in hedonic games, and (4) a winner (source) in a tournament. The computational complexity of unambiguous problems is not well understood, leaving many questions unresolved. We address this gap in a broad complexity-theoretic sense; our main contributions consist of the following.
- We identify three syntactic subclasses of $UΣ_{2}^P$ associated with general properties of problems that guarantee uniqueness: Polynomial Tournament Winner (PTW), Polynomial Condorcet Winner (PCW), and Polynomial Majority Argument (PMA).
- We establish complexity upper and lower bounds for our proposed classes. In particular, we show that they are all contained in $S_2^P$ and are thus significantly easier than the immediate $Σ_{2}^P$ upper bound.
- We characterize the complexity of various practical problems using this framework. In particular, we resolve an open question by Brandt and Bullinger (JAIR '22) and Bullinger and Gilboa (IJCAI '25) concerning strong-popularity in additive hedonic games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19084 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Unambiguous Problems in $Σ^P_2$ Gilboa, Matan Goldberg, Paul W. Koutsoupias, Elias Nisan, Noam Computational Complexity Computer Science and Game Theory F.2; F.0 Various practical problems within the class $Σ_{2}^P$ possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing all unambiguous $Σ_{2}^P$ problems is denoted $UΣ_{2}^P$. Examples include the existence of (1) a dominating strategy in a game, (2) a Condorcet winner, (3) a strongly popular partition in hedonic games, and (4) a winner (source) in a tournament. The computational complexity of unambiguous problems is not well understood, leaving many questions unresolved. We address this gap in a broad complexity-theoretic sense; our main contributions consist of the following. - We identify three syntactic subclasses of $UΣ_{2}^P$ associated with general properties of problems that guarantee uniqueness: Polynomial Tournament Winner (PTW), Polynomial Condorcet Winner (PCW), and Polynomial Majority Argument (PMA). - We establish complexity upper and lower bounds for our proposed classes. In particular, we show that they are all contained in $S_2^P$ and are thus significantly easier than the immediate $Σ_{2}^P$ upper bound. - We characterize the complexity of various practical problems using this framework. In particular, we resolve an open question by Brandt and Bullinger (JAIR '22) and Bullinger and Gilboa (IJCAI '25) concerning strong-popularity in additive hedonic games. |
| title | Complexity of Unambiguous Problems in $Σ^P_2$ |
| topic | Computational Complexity Computer Science and Game Theory F.2; F.0 |
| url | https://arxiv.org/abs/2510.19084 |