TR13-063 Authors: Dung Nguyen, Alan Selman

Publication: 21st April 2013 10:21

Downloads: 2026

Keywords:

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.