Non-autoreducible Sets for NEXP

Authors Dung T. Nguyen, Alan L. Selman



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.590.pdf
  • Filesize: 0.61 MB
  • 12 pages

Document Identifiers

Author Details

Dung T. Nguyen
Alan L. Selman

Cite AsGet 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.
Keywords
  • Autoreducibility
  • NEXP
  • diagonalization
  • structural complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail