Conference item icon

Conference item

Excluding PH Pessiland

Abstract:

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 be sufficient to prove the NP-completeness of the problem GapMINKT^PH of estimating the PH-oracle time-bounded Kolmogorov complexity of a string.
In this work, we analogously define "PH Pessiland" to be a...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Magdalen College
Role:
Author

Contributors

Role:
Editor
More from this funder
Name:
Engineering and Physical Sciences Research Council
Grant:
EP/V048201/1
Publisher:
Dagstuhl Publishing
Host title:
Leibniz International Proceedings in Informatics
Series:
LIPIcs - Leibniz International Proceedings in Informatics
Series number:
13
Volume:
215
Article number:
85
Publication date:
2022-01-26
Acceptance date:
2021-10-31
Event title:
13th Innovations in Theoretical Computer Science Conference
Event location:
Berkeley
Event website:
http://itcs-conf.org/index.html
Event start date:
2022-01-31
Event end date:
2022-02-03
DOI:
ISSN:
1868-8969
ISBN:
9783959772174
Language:
English
Keywords:
Pubs id:
1237072
Local pid:
pubs:1237072
Deposit date:
2022-01-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP