Kleinberg, Robert
[Verfasser:in];
Korten, Oliver
[Verfasser:in];
Mitropolsky, Daniel
[Verfasser:in];
Papadimitriou, Christos
[Verfasser:in]
;
Robert Kleinberg and Oliver Korten and Daniel Mitropolsky and Christos Papadimitriou
[Mitwirkende:r]
Titel:
Total Functions in the Polynomial Hierarchy
Beteiligte:
Kleinberg, Robert
[Verfasser:in];
Korten, Oliver
[Verfasser:in];
Mitropolsky, Daniel
[Verfasser:in];
Papadimitriou, Christos
[Verfasser:in]
Erschienen:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory’s quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes α-PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it, as well as the problem of finding a king in a tournament (a vertex k such that all other vertices are defeated by k, or by somebody k defeated).