ECCC-Report TR13-063https://eccc.weizmann.ac.il/report/2013/063Comments and Revisions published for TR13-063en-usSun, 21 Apr 2013 10:21:01 +0300
Paper TR13-063
| Non-autoreducible Sets for NEXP |
Dung Nguyen,
Alan Selman
https://eccc.weizmann.ac.il/report/2013/063We 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.Sun, 21 Apr 2013 10:21:01 +0300https://eccc.weizmann.ac.il/report/2013/063