1 Search Results for "Selman, Alan L."

Document
DOI: 10.4230/LIPIcs.STACS.2014.590
Non-autoreducible Sets for NEXP

Authors: Dung T. Nguyen and Alan L. Selman

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{nguyen_et_al:LIPIcs.STACS.2014.590,
  author =	{Nguyen, Dung T. and Selman, Alan L.},
  title =	{{Non-autoreducible Sets for NEXP}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{590--601},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.590},
  URN =		{urn:nbn:de:0030-drops-44903},
  doi =		{10.4230/LIPIcs.STACS.2014.590},
  annote =	{Keywords: Autoreducibility, NEXP, diagonalization, structural complexity}
}
  • Refine by Author
  • 1 Nguyen, Dung T.
  • 1 Selman, Alan L.

  • Refine by Classification

  • Refine by Keyword
  • 1 Autoreducibility
  • 1 NEXP
  • 1 diagonalization
  • 1 structural complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact