Complexity of Unambiguous Problems in $Σ^P_2$
This work addresses foundational complexity theory questions for researchers in computational complexity and AI, providing new insights into the structure of unambiguous problems, though it is incremental in building on existing frameworks.
The paper tackles the computational complexity of unambiguous problems in the class Σ2P, which have unique witnesses for yes-instances, by identifying three syntactic subclasses and establishing that they are contained in S2P, making them significantly easier than the general Σ2P upper bound, and resolves an open question about strong-popularity in additive hedonic games.
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.