Excluding PH Pessiland

Heuristica and Pessiland are "worlds" of average-case complexity [Impagliazzo95] that are considered unlikely but that current techniques are unable to rule out. Recently, [Hirahara20] considered a PH (Polynomial Hierarchy) analogue of Heuristica, and showed that to rule it out, it would b...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron: Hirahara, S, Santhanam, R
Awduron Eraill: Braverman, M
Fformat: Conference item
Iaith:English
Cyhoeddwyd: Dagstuhl Publishing 2022