Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-063 | 19th April 2013 23:47

Non-autoreducible Sets for NEXP

RSS-Feed




TR13-063
Authors: Dung Nguyen, Alan Selman
Publication: 21st April 2013 10:21
Downloads: 3054
Keywords: 


Abstract:

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.
Specifically, we show under some polynomial reductions that there is are complete sets for
$\cNEXP$ that are not autoreducible. We obtain the following results:
- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.
- For any positive integers $s$ and $k$ such that $2^s - 1 > k$, there is a $\reduction{p}{s-T}$-complete set for $\cNEXP$ that is not $\reduction{p}{k-tt}$-autoreducible.
- There is a Turing complete set for $\cNEXP$ that is not $\reduction{p}{tt}$-autoreducible.
- For any positive integer $k$, there is a $\reduction{p}{k-tt}$-complete set for $\cNEXP$ that is not weakly $\reduction{p}{k-tt}$-autoreducible.
- There is a $\reduction{p}{3-tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{3-tt}$-autoreducible, given that the autoreduction cannot be allowed to ask a query too short or too long.
- Relative to some oracle, there is a $\reduction{p}{2-T}$-complete set for $\cNEXP$ that is not $\reduction{p}{T}$-autoreducible.
- Relative to some oracle, there is a $\reduction{p}{m}$-complete set for $\cNEXP$ that is not $\reduction{p}{NOR-tt}$-autoreducible.

We will show that settling the question whether every $\reduction{p}{dtt}$-complete set for
$\cNEXP$ is $\reduction{p}{NOR-tt}$-autoreducible
either positively or negatively would lead to major results about the exponential time complexity classes.



ISSN 1433-8092 | Imprint