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.
Expand abstract
In this work, we analogously define "PH Pessiland" to be a...
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, 736.3KB)
-
- Publisher copy:
- 10.4230/LIPIcs.ITCS.2022.85
- Publication website:
- https://drops.dagstuhl.de/opus/institut_lipics.php
Funding
Bibliographic Details
- Publisher:
- Dagstuhl Publishing Publisher's website
- 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
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1237072
- Local pid:
- pubs:1237072
- Deposit date:
- 2022-01-31
Terms of use
- Copyright holder:
- Shuichi Hirahara and Rahul Santhanam
- Copyright date:
- 2022
- Rights statement:
- ©2022 Shuichi Hirahara and Rahul Santhanam; licensed under Creative Commons License CC-BY 4.0
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record