Complexity of Unambiguous Problems in ${\Sigma }_2^P$

Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias +1

Various practical problems within the class ${\Sigma }_2^P$ possess an unambiguity property, meaning that yes-instances correspond with a unique witness. The semantic class containing al…