LFCS Seminar: Tuesday, 23 September: Paul Goldberg | LFCS

Title: Complexity of Unambiguous Problems in Σ^P_2

Abstract: An unambiguous problem is a computational search problem for which any

instance has at most one solution. We are interested in particular in

problems where this uniqueness of solutions is due to the structure of

the problem itself, as opposed to being due to a (hard to verify) promise

that any solution is unique. There are not many such problems in the

class NP (amongst problems that are not known to be polynomial-time

solvable), but there are various interesting ones in the class Σ^P_2.

For example, some are based on the idea that we can design competitions

for which there is at most one winner. With exponentially-many

competitors, we seek a competitor that beats all his opponents: if

"beats" is checkable in polynomial time, we have a Σ^P_2 problem having

at most one solution. Towards classifying the complexity of these

problems, we introduce complexity classes "Polynomial Tournament

Winner" and "Polynomial Condorcet Winner". This is joint work in

progress with Matan Gilboa, Elias Koutsoupias, and Noam Nisan. I will

try to include reminders of definitions of any complexity classes I

refer to, apart from P and NP.