Complexity of Unambiguous Problems in $\hat{I}{\pounds }_2^P$

Abstract

Various practical problems within the class $\hat{I}{\pounds }_2^P$ possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing all unambiguous $\hat{I}{\pounds }_2^P$ problems is denoted $U\hat{I}{\pounds }_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\hat{I}{\pounds }_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 $\hat{I}{\pounds }_2^P$ upper bound. - We characterize the complexity of various practical problems using this framework.

Earlier versions of this work included a preliminary version of the results in arXiv:2607.27277, when the two works formed a single manuscript. 43 pages, 1 figures