LIPIcs.STACS.2014.590.pdf
- Filesize: 0.61 MB
- 12 pages
Document
Non-autoreducible Sets for NEXP
Authors
-
Part of:
Volume:
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-03-05
Cite As Get BibTex
Dung T. Nguyen and Alan L. Selman. Non-autoreducible Sets for NEXP. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 590-601, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.590
Abstract
We investigate autoreducibility properties of complete sets for NEXP under different polynomial-time reductions. Specifically, we show that under some polynomial-time reductions there are complete sets for NEXP that are not autoreducible. We show that settling the question whether every complete set for NEXP under non-adaptative reduction is autoreducible under NOR-truth-table reduction either positively or negatively would lead to major results about the exponential time complexity classes.
Subject Classification
Keywords
- Autoreducibility
- NEXP
- diagonalization
- structural complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads