Separating Complexity Classes Using Autoreducibility.
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle.  We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets for certain levels of the exponential-time hierarchy are autoreducible but there exists some Turing complete set for doubly exponential space that is not.Although we already knew how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Post's program to complexity theory. We feel such techniques may prove unknown separations in the future. In particular, if we could settle the question as to whether all Turing complete sets for doubly exponential time are autoreducible, we would separate either polynomial time from polynomial space, and nondeterministic logarithmic space from nondeterministic polynomial time, or else the polynomial-time hierarchy from exponential time.We also look at the autoreducibility of complete sets under nonadaptive, bounded query, probabilistic, and nonuniform reductions. We show how settling some of these autoreducibility questions will also lead to new complexity class separations.
Introduction
While complexity theorists have made great strides in understanding the structure of complexity
classes, they have not yet found the proper tools to do nontrivial separation of complexity classes
such as P and NP. They have developed sophisticated diagonalization, combinatorial and algebraic
techniques but none of these ideas have yet proven very useful in the separation task.
Back in the early days of computability theory, Post [13] wanted to show that the set of noncomputable
computably enumerable sets strictly contains the Turing-complete computably enumerable
sets. In what we now call iPost's Programj (see [11, 15]), Post tried to show these classes dioeer by
-nding a property that holds for all sets in the -rst class but not for some set in the second.
We would like to resurrect Post's Program for separating classes in complexity theory. In
particular we will show how some classes dioeer by showing that their complete sets have dioeerent
structure. While we do not separate any classes not already separable by known diagonalization
techniques, we feel that re-nements to our techniques may yield some new separation results.
In this paper we will concentrate on the property known as iautoreducibility.j A set A is
autoreducible if we can decide whether an input x belongs to A in polynomial-time by making
queries about membership of strings dioeerent from x to A.
Trakhtenbrot [16] -rst looked at autoreducibility in both the unbounded and space-bounded
models. Ladner [10] showed that there exist Turing-complete computably enumerable sets that are
not autoreducible. Ambos-Spies [1] -rst transferred the notion of autoreducibility to the polynomial-time
setting. More recently, Yao [19] and Beigel and Feigenbaum [5] have studied a probabilistic
variant of autoreducibility known as icoherence.j
In this paper, we ask for what complexity classes do all the complete sets have the autoreducibil-
ity property. In particular we show:
ffl All Turing-complete sets for \Delta EXP
are autoreducible for any constant k, where \Delta EXP
the sets that are exponential-time Turing-reducible to \Sigma P
k .
ffl There exists a Turing-complete set for doubly exponential space that is not autoreducible.
Since the union of all sets \Delta EXP
k coincides with the exponential-time hierarchy, we obtain a separation
of the exponential-time hierarchy from doubly exponential space and thus of the polynomial-time
hierarchy from exponential space. Although these results also follow from the space hierarchy
theorems [9] which we have known for a long time, our proof does not directly use diagonalization,
rather separates the classes by showing that they have dioeerent structural properties.
Issues of relativization do not apply to this work because of oracle access (see [8]): A polynomial-time
autoreduction can not view as much of the oracle as an exponential or doubly exponential
computation. To illustrate this point we show that there exists an oracle relative to which some
complete set for exponential time is not autoreducible.
Note that if we can settle whether the Turing-complete sets for doubly exponential time are
all autoreducible one way or the other, we will have a major separation result. If there exists
a Turing-complete set for doubly exponential time that is not autoreducible, then we get that the
exponential-time hierarchy is strictly contained in doubly exponential time thus that the polynomial-time
hierarchy is strictly contained in exponential time. If all of the Turing-complete sets for doubly
exponential time are autoreducible, we get that doubly exponential time is strictly contained in doubly
exponential space, and thus polynomial time strictly in polynomial space. We will also show that
this assumption implies a separation of nondeterministic logarithmic space from nondeterministic
polynomial time. Similar implications hold for space bounded classes (see Section 5). Autoreducibil-
ity questions about doubly exponential time and exponential space thus remain an exciting line of
research.
We also study the nonadaptive variant of the problem. Our main results scale down one exponential
as follows:
ffl All truth-table-complete sets \Delta P
are truth-table-autoreducible for any constant k, where \Delta P
denotes that sets polynomial-time Turing-reducible to \Sigma P
k .
ffl There exists a truth-table-complete set for exponential space that is not truth-table-autoreducible.
Again, -nding out whether all truth-table-complete sets for intermediate classes, namely polynomial
space and exponential time, are truth-table-autoreducible, would have major implications.
In contrast to the above results we exhibit the limitations of our approach: For the restricted
reducibility where we are only allowed to ask two nonadaptive queries, all complete sets for EXP,
EXPSPACE, EEXP, EEXPSPACE, etc., are autoreducible.
We also argue that uniformity is crucial for our technique of separating complexity classes, because
our nonautoreducibility results fail in the nonuniform setting. Razborov and Rudich [14] show
that if strong pseudo-random generators exist, inatural proofsj can not separate certain nonuniform
complexity classes. Since this paper relies on uniformity in an essential way, their result does not
apply.
Regarding the probabilistic variant of autoreducibility mentioned above, we can strengthen
our results and construct a Turing-complete set for doubly exponential space that is not even
probabilistically autoreducible. We leave the analogue of this theorem in the nonadaptive setting
open: Does there exist a truth-table complete set for exponential space that is not probabilistically
truth-table autoreducible? We do show that every truth-table complete set for exponential time
is probabilistically truth-table autoreducible. So, a positive answer to the open question would
establish that exponential time is strictly contained in exponential space. A negative answer, on the
other hand, would imply a separation of nondeterministic logarithmic space from nondeterministic
polynomial time.
Here is the outline of the paper: First, we introduce our notation and state some preliminaries in
Section 2. Next, in Section 3 we establish our negative autoreducibility results, for the adaptive as
well as the nonadaptive case. Then we prove the positive results in Section 4, where we also brieAEy
look at the randomized and nonuniform settings. Section 5 discusses the separations that follow
from our results and would follow from improvements on them. Finally, we conclude in Section 6
and mention some possible directions for further research.
1.1 Errata to conference version
A previous version of this paper [6] erroneously claimed proofs showing all Turing complete sets
for EXPSPACE are autoreducible and all truth-table complete sets for PSPACE are nonadaptively
autoreducible. Combined with the additional results in this version, we would have a separation of
NL and NP (see Section 5).
However the proofs in the earlier version failed to account for the growth of the running time
when recursively computing previous players' moves. We use the proof technique in Section 3 though
unfortunately we get weaker theorems. The original results claimed in the previous version remain
important open questions as resolving them either way will yield new separation results.
Notation and Preliminaries
Most of our complexity theoretic notation is standard. We refer the reader to the textbooks by
Balc#zar, D#az and Gabarr# [4, 3], and by Papadimitriou [12].
We use the binary alphabet 1g. We denote the dioeerence of a set A with a set B, i.e.,
the subset of elements of A that do not belong to B, by A n B.
For any integer k ? 0, a \Sigma k -formula is a Boolean expression of the form
where OE is a Boolean formula, Q i denotes 9 if i is odd, and 8 otherwise, and the n i 's are positive
integers. We say that (1) has alternations. A \Pi k -formula is just like (1) except starts with a
8-quanti-er. It also has k \Gamma 1 alternations. A QBF k -formula is a \Sigma k -formula (1) or a \Pi k -formula
For any integer k ? 0, \Sigma P
k denotes the k-th \Sigma-level of the polynomial-time hierarchy. We
de-ne these levels recursively by \Sigma P
k . The \Delta-levels of the polynomial-time
and exponential-time hierarchy are de-ned as \Delta P
respectively \Delta EXP
k . The
polynomial-time hierarchy PH equals the union of all sets \Delta P
k , and the exponential-time hierarchy
EXPH similarly the union of all sets \Delta EXP
k .
A reduction of a set A to a set B is a polynomial-time oracle Turing machine M such that
A. We say that A reduces to B and write A 6 P
Turing). The reduction M
is nonadaptive if the oracle queries M makes on any input are independent of the oracle, i.e., the
queries do not depend upon the answers to previous queries. In that case we write A 6 P
for truth-table). Reductions of functions to sets are de-ned similarly. If the number of queries on
an input of length n is bounded by q(n), we write A 6 P
bounded by some constant, we write A 6 P
We denote the set of queries of
M on input x with oracle B by Q M B(x); in case of nonadaptive reductions, we omit the oracle B in
the notation. If the reduction asks only one query and answers the answer to that query, we write
For any reducibility 6 P
r and any complexity class C, a set C is 6 P
r -hard for C if we can 6 P
r -reduce
every set A 2 C to C. If in addition C 2 C, we call C 6 P
r -complete for C. For any integer k ? 0, the
set TQBF k of all true QBF k -formulae is 6 P
m -complete for \Sigma P
k . For reduces to the fact
that the set SAT of satis-able Boolean formulae is 6 P
m -complete for NP.
Now we get to the key concept of this paper:
De-nition 2.1 A set A is autoreducible if there is a reduction M of A to itself that never queries its
own input, i.e., for any input x and any oracle B, x 62 Q M B(x). We call such M an autoreduction
of A.
We will also discuss randomized and nonuniform variants. A set is probabilistically autoreducible if it
has a probabilistic autoreduction with bounded two-sided error. Yao [19] -rst studied this concept
under the name icoherencej. A set is nonuniformly autoreducible if it has an autoreduction that uses
polynomial advice. For all these notions, we can consider both the adaptive and the nonadaptive
case. For randomized autoreducibility, nonadaptiveness means that the queries only depend on the
input and the random seed.
3 Nonautoreducibility Results
In this section, we show that large complexity classes have complete sets that are not autoreducible.
Theorem 3.1 There is a 6 P
2\GammaT -complete set for EEXPSPACE that is not autoreducible.
Most natural classes containing EEXPSPACE, e.g., EEEXPTIME and EEEXPSPACE, also have
this property.
We can even construct the complete set in Theorem 3.1 to defeat every probabilistic autoreduc-
tion:
Theorem 3.2 There is a 6 P
2\GammaT -complete set for EEXPSPACE that is not probabilistically autore-
ducible.
In the nonadaptive setting, we obtain:
Theorem 3.3 There is a 6 P
3\Gammatt -complete set for EXPSPACE that is not nonadaptively autore-
ducible.
Unlike the case of Theorem 3.1, our construction does not seem to yield a truth-table complete set
that is not probabilistically nonadaptively autoreducible. In fact, as we shall show in Section 4.3,
such a result would separate EXP from EXPSPACE. See also Section 5.
We will detail in Section 4.3 that our nonautoreducibility results do not hold in the nonuniform
setting.
3.1 Adaptive Autoreductions
Suppose we want to construct a nonautoreducible Turing-complete set for a complexity class C, i.e.,
a set A such that:
1. A is not autoreducible.
2. A is Turing-hard for C.
3. A belongs to C.
If C has a 6 P
m -complete set K, realizing goals 1 and 2 is not too hard: We can encode K in A,
and at the same time diagonalize against all autoreductions. A straightforward implementation
would be to encode K(y) as A(h0; yi), and stage-wise diagonalize against all 6 P
-reductions M by
picking for each M an input x not of the form h0; yi that is not queried during previous stages, and
setting (x). However, this construction does not seem to achieve the third goal.
In particular, deciding the membership of a diagonalization string x to A might require computing
inputs y of length jxj c , assuming M runs in time n c . Since we have to do this
for all potential autoreductions M , we can only bound the resources (time, space) needed to decide
A by a function in t(n !(1) ), where t(n) denotes the amount of resources some deterministic Turing
machine accepting K uses. That does not suOEce to keep A inside C.
To remedy this problem, we will avoid the need to compute K(y) on large inputs y, say of length
at least jxj. Instead, we will make sure we can encode the membership of such strings to any set,
not just K, and at the same time diagonalize against M on input x. We will argue that we can do
this by considering two possible coding regions at every stage as opposed to a -xed one: the left
region L, containing strings of the form h0; yi, and the right region R, similarly containing strings
of the form h1; yi. The following states that we can use one of the regions to encode an arbitrary
sequence, and set the other region such that the output of M on input x is -xed and indicates the
region used for encoding.
Either it is the case that for any setting of L there is a setting of R such that M A (x)
accepts, or for any setting of R there is a setting of L such that M A (x) rejects. (*)
This allows us to achieve goals 1 and 2 from above as follows. In the former case, we will set
encode K in L (at that stage); otherwise we will set encode K in R.
Since the value of A(x) does not aoeect the behavior of M A on input x, we diagonalize against M
in both cases. Also, in any case
so deciding K is still easy when given A. Moreover - and crucially - in order to compute A(x), we
no longer have to decide K(y) on large inputs y, of length jxj or more. Instead, we have to check
whether the former case in (*) holds or not. Although quite complex a task, it only depends on
M and on the part of A constructed so far, not on the value of K(y) for any input of length jxj
or more: We verify whether we can encode any sequence, not just the characteristic sequence of
K for lengths at least jxj, and at the same time diagonalize against M on input x. Provided the
complexity class C is suOEciently powerful, we can perform this task in C.
There is still a catch, though. Suppose we have found out that the former case in (*) holds.
Then we will use the left region L to encode K (at that stage), and we know we can diagonalize
against M on input x by setting the bits of the right region R appropriately. However, deciding
exactly how to set these bits of the noncoding region requires, in addition to determining which
region we should use for coding, the knowledge of K(y) for all y such that jxj 6 jyj 6 jxj c . In order
to also circumvent the need to decide K for too large inputs here, we will use a slightly stronger
version of (*) obtained by grouping quanti-ers into blocks and rearranging them. We will partition
the coding and noncoding regions into intervals. We will make sure that for any given interval, the
length of a string in that interval (or any of the previous intervals) is no more than the square of the
length of any string in that interval. Then we will block-wise alternately set the bits in the coding
region according to K, and the corresponding ones in the noncoding region so as to maintain the
diagonalization against M on input x as in (*). This way, in order to compute the bit A(h1; zi)
of the noncoding region, we will only have to query K on inputs y with jyj 6 jzj 2 , as opposed to
for an arbitrarily large c depending on M as was the case before.
This is what happens in the next lemma, which we prove in a more general form, because we
will need the generalization later on in Section 5.
Lemma 3.4 Fix a set K, and suppose we can decide it simultaneously in time t(n) and space
s(n). be a constructible monotone unbounded function, and suppose there is
a deterministic Turing machine accepting TQBF that takes time t 0 (n) and space s 0 (n) on QBF-
formulae of size 2 n fi(n)
with at most 2 log fi(n) alternations. Then there is a set A such that:
1. A is not autoreducible.
2. K 6 P
A.
3. We can decide A simultaneously in time O(2 n 2
\Deltat(n 2 )+2 n \Deltat 0 (n)) and space O(2 n 2
Proof (of Lemma 3.4)
Fix a function fi satisfying the hypotheses of the Lemma. Let M be a standard enumeration
of autoreductions clocked such that M i runs in time n fi(i) on inputs of length n. Our construction
starts out with A being the empty set, and then adds strings to A in subsequent stages
de-ned by the following sequence:
Note that since M i runs in time n fi(i) , M i can not query strings of length n i+1 or more on input 0 n i .
Fix an integer i ? 1 and let . For any integer j such that 0 6 j 6 log fi(m), let I j
denote the set of all strings with lengths in the interval [m 2 j
1)). Note that
log fi(m)
forms a partition of the set I of strings with lengths in [m; m fi(m)
the property that for any 0 6 k 6 log fi(m), the length of any string in [ k
I j is no more than the
square of the length of any string in I k .
During the i-th stage of the construction, we will encode the restriction Kj I of K to I into
use the string 0 m for diagonalizing against M i , applying the next
strengthening of (*) to do so:
3.1 For any set A, at least one of the following holds:
or
Here we use (Q z y ) y2Y as a shorthand for Q z y 1
and
all variables are quanti-ed over f0; 1g. Without loss of generality we assume that the range of the
pairing function h\Delta; \Deltai is disjoint from 0   .
Proof (of Claim 3.1)
Fix A. If (2) does not hold, then its negation holds, i.e,
Switching the quanti-ers log fi(m) in (4) yields
the weaker statement (3).
if formula (2) holds
then for
the lexicographically -rst value satisfying
where A
endfor
A
the lexicographically -rst value satisfying
where A
endfor
A
endif

Figure

1: Stage i of the construction of the set A in Lemma 3.4

Figure

1 describes the i-th stage in the construction of the set A. Note that the lexicographically
-rst values in this algorithm always exist, so the construction works -ne. We now argue that the
resulting set A satis-es the properties of Lemma 3.4.
1. The construction guarantees that by the end of stage
Since M i on input 0 m can not query 0 m (because M i is an autoreduction) nor any of the
strings added during subsequent stages (because M i does not even have the time to write
down any of these strings), A(0 m
holds for the -nal set A. So, M i is not an
autoreduction of A. Since this is true of any autoreduction M i , the set A is not autoreducible.
2. During stage i, we encode Kj I in the left region ioe we do not put 0 m into A; otherwise
we encode Kj I in the right region. So, for any y 2 I , Therefore,
A.
3. First note that A only contains strings of the form 0 m with
and strings of the form hb; yi with b 2 f0; 1g and y 2 \Sigma   .
Assume we have executed the construction of A up to but not including stage i. The additional
work to decide the membership to A of a string belonging to the i-th stage, is as follows.
case
does not hold and (2) is a QBF 2 log fi(m) -formula of size
case hb; zi where
Then hb; zi 2 A ioe z 2 K, which we can decide in time t(jzj).
case hb; zi where
Say z 2 I k , 0 6 k 6 log fi(m). In order to compute whether hb; zi 2 A, we run the part of
stage i corresponding to the values of j in Figure 1 up to and including k. This involves
computing K on [ k
I j and deciding O(2 jzj ) QBF 2 log fi(m) -formulae of size O(2 m fi(m) ).
The latter takes O(2 jzj \Delta t 0 (m)) time. Since every string in [ k
I j is of size no more than
, we can do the former in time O(2 jzj 2
A similar analysis also shows that we can perform the stages up to but not including i in time
All together, this yields the time bound claimed for A. The analysis of the space complexity
is analogous.
(Lemma
Using the upper bound 2 n fi(n) for s 0 (n), the smallest standard complexity class to which Lemma
3.4 applies, seems to be EEXPSPACE. This results in Theorem 3.1.
Proof (of Theorem 3.1)
In Lemma 3.4, set K a 6 P
m -complete set for EEXPSPACE, and
In section 4.2, we will see that 6 P
2\GammaT in the statement of Theorem 3.1 is optimal: Theorem 4.5
shows that Theorem 3.1 fails for 6 P
2\Gammatt .
We note that the proof of Theorem 3.1 carries through for 6 EXPSPACE
-reductions with polynomially
bounded query lengths. This implies the strengthening given by Theorem 3.2.
3.2 Nonadaptive Autoreductions
Diagonalizing against nonadaptive autoreductions M is easier. If M runs in time -(n), there can
be no more than -(n) coding strings that interfere with the diagonalization, as opposed to 2 -(n) in
the adaptive case. This allows us to reduce the complexity of the set constructed in Lemma 3.4 as
follows.
Lemma 3.5 Fix a set K, and suppose we can decide it simultaneously in time t(n) and space
s(n). be a constructible monotone unbounded function, and suppose there is
a deterministic Turing machine accepting TQBF that takes time t 0 (n) and space s 0 (n) on QBF-
formulae of size n fi(n) with at most 2 log fi(n) alternations. Then there is a set A such that:
1. A is not nonadaptively autoreducible.
2. K 6 P
A.
3. We can decide A simultaneously in time O(2 n \Delta (t(n 2 )+ t 0 (n))) and space O(2 n +s(n 2 )+s 0 (n)).
Proof (of Lemma 3.5)
The construction of the set A is the same as in Lemma 3.4 (see Figure 1) apart from the following
dioeerences:
now is a standard enumeration of nonadaptive autoreductions clocked such that
runs in time n fi(i) on inputs of length n. Note that the set QM (x) of possible queries M
makes on input x contains no more than jxj fi(i) elements.
ffl During stage i ? 1 of the construction, I denotes the set of all strings y with lengths in
denotes the set of strings in I with lengths in [m
Note that the only ' y 's and r y 's that aoeect the validity of the predicate iM A 0
formula (2) and the corresponding formulae in Figure 1, are those for which y 2 I .
ffl At the end of stage i in Figure 1, we add the following line:
A
This ensures coding K(y) for strings y with lengths in [n are
queried by M i on input 0 m . Although not essential, we choose to encode them in both the
left and the right region.
Adjusting time and space bounds appropriately, the proof that A satis-es the 3 properties claimed,
carries over. There is an additional case in the analysis of the third point, namely the one of an
input of the form hb; zi where b 2 I . Then, by construction,
which we can decide in time t(jzj). The crucial simpli-cation over the adaptive
case lies in the fact that (2) and the similar formulae in Figure 1 now become QBF 2 log fi(n) -formulae
of size O(n fi(n) ) as opposed to of size O(2 n fi(n) ) in Lemma 3.4. (Lemma 3.5)
As a consequence, we can lower the space complexity in the equivalent of Theorem 3.1 from
doubly exponential to singly exponential, yielding Theorem 3.3. In section 4.2, we will show we can
not reduce the number of queries from 3 to 2 in Theorem 3.3.
If we restrict the number of queries the nonadaptive autoreduction is allowed to make to some
-xed polynomial, the proof technique of Theorem 3.3 also applies to EXP. In particular, we obtain:
Theorem 3.6 There is a 6 P
3\Gammatt -complete set for EXP that is not 6 P
btt -autoreducible.
4 Autoreducibility Results
For small complexity classes, all complete sets turn out to be autoreducible. Beigel and Feigenbaum
[5] established this property of all levels of the polynomial-time hierarchy as well as of PSPACE,
the largest class for which it was known to hold before our work. In this section, we will prove it
for the \Delta-levels of the exponential-time hierarchy.
As to nonadaptive reductions, the question was even open for all levels of the polynomial-time
hierarchy. We will show here that the 6 P
tt -complete sets for the \Delta-levels of the polynomial-time
hierarchy are nonadaptively autoreducible. For any complexity class containing EXP, we will prove
that the 6 P
2\Gammatt -complete sets are 6 P
2\Gammatt -autoreducible.
Finally, we will also consider nonuniform and randomized autoreductions.
Throughout this section, we will assume without loss of generality an encoding fl of a computation
of a given oracle Turing machine M on a given input x with the following properties. fl will
be a marked concatenation of successive instantaneous descriptions of M , starting with the initial
instantaneous description of M on input x, such that:
ffl Given a pointer to a bit in fl, we can -nd out whether that bit represents the answer to an
oracle query by probing a constant number of bits of fl.
ffl If it is the answer to an oracle query, the corresponding query is a substring of the pre-x of
fl up to that point, and we can easily compute a pointer to the beginning of that substring
without probing fl any further.
ffl If it is not the answer to an oracle query, we can perform a local consistency check for that
bit which only depends on a constant number of previous bit positions of fl and the input x.
Formally, there exist a function g M and a predicate e M , both polynomial-time computable,
and a constant c M such that the following holds: For any input x, any index i to a bit position
in fl, and any j, 1 is an index no larger than i, and
indicates whether fl passes the local consistency test for its i-th bit fl i . Provided the pre-x
of fl up to but not including position i is correct, the local consistency test is passed ioe fl i is
correct.
We call such an encoding a valid computation of M on input x ioe the local consistency tests (5) for
all the bit positions i that do not correspond to oracle answers, are passed, and the other bits equal
the oracle's answer to the corresponding query. Any other string we will call a computation.
4.1 Adaptive Autoreductions
We will -rst show that every 6 P
T -complete set for EXP is autoreducible, and then generalize to all
\Delta-levels of the exponential-time hierarchy.
Theorem 4.1 Every 6 P
T -complete set for EXP is autoreducible.
Here is the proof idea: For any of the standard deterministic complexity classes C, we can decide
each bit of the computation on a given input x within C. So, if A is a 6 P
T -complete set for C that
can be decided by a machine M within the con-nes of the class C, then we can 6 P
-reduce deciding
the i-th bit of the computation of M on input x to A. Now, consider the two (possibly invalid)
computations we obtain by applying for every bit position the above reduction, answering all queries
except for x according to A, and assuming x 2 A for one computation, and x 62 A for the other.
Note that the computation corresponding to the right assumption about A(x), is certainly
correct. So, if both computations yield the same answer (which we can eOEciently check using A
without querying x), that answer is correct. If not, the other computation contains a mistake. We
can not check both computations entirely to see which one is right, but given a pointer to the -rst
incorrect bit of the wrong computation, we can eOEciently verify that it is mistaken by checking only
a constant number of bits of that computation. The pointer is again computable within C.
In case C ' EXP, using a 6 P
T -reduction to A and assuming x 2 A or x 62 A as above, we
can determine the pointer with oracle A (but without querying x) in polynomial time, since the
pointer's length is polynomially bounded.
We now -ll out the details.
Proof (of Theorem 4.1)
Fix a 6 P
T -complete set A for EXP. Say A is accepted by a Turing machine M such that the
computation of M on an input of size n has length 2 p(n) for some -xed polynomial p. Without loss
of generality the last bit of the computation gives the -nal answer. Let g M , e M , and c M be the
formalization of the local consistency test for M as described by (5).
Let -(hx; ii) denote the i-th bit of the computation of M on input x. We can compute - in
EXP, so there is an oracle Turing machine R - 6 P
-reducing - to A.
Let oe(x) be the -rst such that R Anfxg
exists. Again, we can compute oe in EXP, so there is a 6 P
T -reduction R oe from oe to A.
Consider the algorithm in Figure 2 for deciding A on input x. The algorithm is a polynomial-time
oracle Turing machine with oracle A that does not query its own input x. We now argue that
it correctly decides A on input x. We distinguish between two cases:
case R Anfxg
Since at least one of the computations R Anfxg
- (hx; \Deltai) or R A[fxg
coincides with the actual
computation of M on input x, and the last bit of the computation equals the -nal decision,
correctness follows.
if R Anfxg
then accept ioe R A[fxg
else i / R A[fxg
oe (x)
accept ioe e M (x;
endif

Figure

2: Autoreduction for the set A of Theorem 4.1 on input x
case R Anfxg
contains a mistake. Variable i gets the
correct value of the index of the -rst incorrect bit in this computation, so the local consistency
test for R Anfxg
being the computation of M on input x fails on the i-th bit, and we
accept x.
If x 62 A, R Anfxg
- (hx; \Deltai) is a valid computation, so no local consistency test fails, and we reject
x.
(Theorem 4.1)
The local checkability property of computations used in the proof of Theorem 4.1 does not
relativize, because the oracle computation steps depend on the entire query, i.e., on a number of
bits that is only limited by the resource bounds of the base machine, in this case exponentially
many. We next show that Theorem 4.1 itself also does not relativize.
Theorem 4.2 Relative to some oracle, EXP has a 6 P
2\GammaT -complete set that is not autoreducible.
Proof
Note that EXP has the following property:
Property 4.1 There is an oracle Turing machine N running in EXP such that for any oracle B,
the set accepted by N B is 6 P
m -complete for EXP B .
Without loss of generality, we assume that N runs in time 2 n . Let K B denote the set accepted by
We will construct an oracle B and a set A such that A is 6 P
2\GammaT -complete for EXP B and is not
The construction of A is the same as in Lemma 3.4 (see Figure 1) with
for that the reductions M i now also have access to the oracle B.
We will encode in B information about the construction of A that reduces the complexity of A
relative to B, but do it high enough so as not to destroy the 6 P
2\GammaT -completeness of A for EXP B nor
the diagonalizations against 6 P B
-autoreductions.
We construct B in stages along with A. We start with B empty. Using the notation of Lemma
3.4, at the beginning of stage i, we add
to B ioe property (2) does not hold, and at the end of
sub-stage j, we union B with
(2) holds at stage i
Note that this does not aoeect the value of K B (y) for
, nor the computations of M i on
inputs of size at most m (for suOEciently large i such that m log It follows from the analysis
in the proof of Lemma 3.4 that the set A is 6 P
2\GammaT -hard for EXP B and not 6 P B
Regarding the complexity of deciding A relative to B, note that the encoding in the oracle B
allows us to eliminate the need for evaluating QBF log fi(n) -formulae of size 2 n fi(n)
. Instead, we just
query B on easily constructed inputs of size O(2 n 2
Therefore, we can drop the terms corresponding
to the QBF log fi(n) -formulae of size 2 n fi(n) in the complexity of A. Consequently, A 2 EXP B .
(Theorem 4.2)
Theorem 4.2 applies to any complexity class containing EXP that has Property 4.1, e.g.,
EXPSPACE, EEXP, EEXPSPACE, etc.
Sometimes, the structure of the oracle allows to get around the lack of local checkability of oracle
queries. This is the case for oracles from the polynomial-time hierarchy, and leads to the following
extension of Theorem 4.1:
Theorem 4.3 For any integer k ? 0, every 6 P
T -complete set for \Delta EXP
k+1 is autoreducible.
The proof idea is as follows: Let A be a 6 P
T -complete set accepted by the deterministic oracle Turing
machine M with oracle TQBF k . First note that there is a polynomial-time Turing machine N such
that a query q belongs to the oracle TQBF k ioe
where the y ' 's are of size polynomial in jqj.
We consider the two purported computations of M on input x constructed in the proof of
Theorem 4.1. One of them belongs to a party assuming x 2 A, the other one to a party assuming
x 62 A. The computation corresponding to the right assumption is correct; the other one might not
be.
Now, suppose the computations dioeer, and we are given a pointer to the -rst bit position
where they disagree, which turns out to be the answer to an oracle query q. Then we can have
the two parties play the k-round game underlying (6): The party claiming q 2 TQBF k plays the
existentially quanti-ed y ' 's, the other one the universally quanti-ed y ` 's. The players' strategies will
consist of computing the game history so far, determining their optimal next move, 6 P
-reducing
this computation to A, and -nally producing the result of this reduction under their respective
assumption about A(x). This will guarantee that the party with the correct assumption plays
optimally. Since this is also the one claiming the correct answer to the oracle query q, he will win
the game, i.e., N(q; y answer bit.
The only thing the autoreduction for A has to do, is determine the value of N(q; y
in polynomial time using A as an oracle but without querying x. It can do that along the lines
of the base case algorithm given in Figure 2. If during this process, the local consistency test for
's computation requires the knowledge of bits from the y ` 's, we compute these via the reduction
de-ning the strategy of the corresponding player. The bits from q we need, we can retrieve from the
M-computations, since both computations are correct up to the point where they -nished generating
q. Once we know N(q; y easily decide the correct assumption about A(x).
The construction hinges on the hypothesis that we can 6 P
-reduce determining the player's moves
to A. Computing these moves can become quite complex, though, because we have to recursively
reconstruct the game history so far. The number of rounds k being constant, seems crucial for
keeping the complexity under control. The conference version of this paper [6] erroneously claimed
the proof works for EXPSPACE, which can be thought of as alternating exponential time with
an exponential number of alternations. Establishing Theorem 4.3 for EXPSPACE would actually
separate NL from NP, as we will see in Section 5.
Proof (of Theorem 4.3)
Let A be a 6 P
T -complete set for \Delta EXP
k accepted by the exponential-time oracle Turing
machine M with oracle TQBF k . Let g M , e M , and c M be the formalization of the local consistency
test for M as described by (5). Without loss of generality there is a polynomial p and a polynomial-time
Turing machine N such that on inputs of size n, M makes exactly 2 p(n) oracle queries, all of
the form
where q has length 2 p 2 (n) . Moreover, the computations of N in (7) each have length 2 p 3 (n) , and
their last bit represents the answer; the same holds for the computations of M on inputs of length
n. Let g N , e N , and c N be the formalization of the local consistency test for N .
We -rst de-ne a bunch of functions computable in \Delta EXP
k+1 . For each of them, say -, we -x an
oracle Turing machine R - that 6 P
-reduces - to A, and which the -nal autoreduction for A will use.
The proofs that we can compute these functions in \Delta EXP
are straightforward.
Let -(hx; ii) denote the i-th bit of the computation of M TQBF k on input x, and oe(x) the -rst i
(if any) such that R Anfxg
ii). The roles of - and oe are the same as in the proof
of Theorem 4.1: We will use R - to -gure out whether both possible answers for the oracle query
lead to the same -nal answer, and if not, use R oe to -nd a pointer i to the -rst incorrect
bit (in any) of the simulated computation getting the negative oracle answer x 62 A. If i turns out
not to point to an oracle query, we can proceed as in the proof of Theorem 4.1. Otherwise, we will
make use of the following functions and associated reductions to A.
We de-ne the functions j ' and y ' inductively for At each level ' we -rst de-ne j ' ,
which induces a reduction R j ' , and then de-ne y ' based on R j ' . All of these functions take an input
x such that the i-th bit of R Anfxg
- (hx; \Deltai) is the answer to an oracle query (7), where
oe (x).
We de-ne j ' (x) as the lexicographically least y
such that
if this value does not exist, we set j '
. Note that the right-hand side of (8) is 1 ioe y ' is
existentially quanti-ed in (7).
R A[fxg
R Anfxg
The condition on the right-hand side of (9) means that we use the hypothesis x 2 A to compute
y ' (x) from R j ' in case:
ffl either y ' is existentially quanti-ed in (7) and the player assuming x 2 A claims (7) holds,
ffl or else y ' is universally quanti-ed and the player assuming x 2 A claims (7) fails.
Otherwise we use the hypothesis x 62 A.
In case i points to the answer to an oracle query (7), the functions j ' and the reductions R j '
incorporate the moves during the successive rounds of the game underlying (7). The reduction R j '
together with the player's assumption about membership of x to A, determines the actual move
during the '-th round, namely R A[fxg
if the '-th round is played by the opponent assuming
otherwise. The condition on the right-hand side of (9) guarantees that the
existentially quanti-ed variables are determined by the opponent claiming the query (7) is a true
formula, and the universally quanti-ed ones by the other opponent. In particular, (9) ensures that
the opponent with the correct claim about (7) has a wining strategy. Provided it exists, the function
de-nes a winning move during the '-th round of the game for the opponent playing that round,
given the way the previous rounds were actually played (as described by the y(x)'s). For odd ',
i.e., y ' is existentially quanti-ed, it tries to set y ' such that the remainder of (7) holds; otherwise it
tries to set y ' such that the remainder of (7) fails. The actual move may dioeer from the one given
by j ' in case the player's assumption about x 2 A is incorrect. The opponent with the correct
assumption plays according to j ' . Since that opponent also makes the correct claim about (7), he
will win the game. In any case, N(q; y hold ioe (7) holds.
Finally, we de-ne the functions - and - , which have a similar job as the functions - respectively
oe, but for the computation of N(q; y instead of the computation of M TQBF
k (x). More
precisely, -(hx; ri) equals the r-th bit of the computation of N(q; y 1 where the
are de-ned by (9), and the bit with index
oe (x) in the computation R Anfxg
the answer to the oracle query (7). We de-ne -(x) to be the -rst r (if any) for which R Anfxg
R A[fxg
ri), provided the bit with index
oe (x) in the computation R Anfxg
- (hx; \Deltai) is the
answer to an oracle query.
Now we have these functions and corresponding reductions, we can describe an autoreduction for
A. On input x, it works as described in Figure 3. We next argue that the algorithm correctly decides
A on input x. Checking the other properties required of an autoreduction for A is straightforward.
We only consider the cases where R Anfxg
points to the
answer to an oracle query in R Anfxg
\Deltai). We refer to the analysis in the proof of Theorem 4.1
for the remaining cases.
case R Anfxg
points to the -rst incorrect bit of R Anfxg
- (hx; \Deltai), which turns out to be the
answer to an oracle query, say (7).
yields the correct oracle answer
to (7),
R Anfxg
and we accept x.
If x 62 A, both R Anfxg
give the correct answer to the oracle
query i points to in the computation R Anfxg
\Deltai). So, they are equal, and we reject x.
if R Anfxg
then accept ioe R A[fxg
else i / R A[fxg
oe (x)
if the i-th bit of R Anfxg
\Deltai) is not the answer to an oracle query
then accept ioe e M (x;
else if R Anfxg
then accept ioe R Anfxg
else r / R A[fxg
accept ioe e N (q; y
R Anfxg
where q denotes the query described in R Anfxg
to which the i-th bit in this computation is the answer
and
R A[fxg
R Anfxg
endif
endif
endif

Figure

3: Autoreduction for the set A of Theorem 4.3 on input x
case R Anfxg
Then, as described in Figure 3, we will use the local consistency test for R Anfxg
being the
computation of N(q; y 1 (x)). Apart from bits in the purported computation
R Anfxg
- (hx; \Deltai), this test may also need bits from q and from the y ' (x)'s. The y ` (x)'s can be
computed straightforwardly using their de-nition (9). The bits from q we might need, can be
retrieved from R Anfxg
\Deltai). This is because our encoding scheme for computations has the
property that the query q is a substring of the pre-x of the computation up to the position
indexed by i. Since either R Anfxg
- (hx; \Deltai) is correct everywhere, or else i is the -rst position
where is is incorrect, the description of q in R Anfxg
- (hx; \Deltai) is correct in any case. Moreover,
we can easily compute a pointer to the beginning of the substring q of R Anfxg
- (hx; \Deltai) from i.
- (hx; \Deltai) has an error as a computation of
gets assigned the index of the -rst incorrect bit in
this computation, so the local consistency check fails, and we accept x.
If x 62 A, R Anfxg
- (hx; \Deltai) is a valid computation of N(q; y 1 so every local
consistency test is passed, and we reject x.
(Theorem 4.3)
4.2 Nonadaptive Autoreductions
So far, we constructed autoreductions for 6 P
T -complete sets A. On input x, we looked at the
two candidate computations obtained by reducing to A, answering all oracle queries except for x
according to A, and answering query x positively for one candidate, and negatively for the other.
If the candidates disagreed, we tried to -nd out the right one, which always existed. We managed
to get the idea to work for quite powerful sets A, e.g., EXP-complete sets, by exploiting the local
checkability of computations. That allowed us to -gure out the wrong computation without going
through the entire computation ourselves: With help from A, we -rst computed a pointer to the
-rst mistake in the wrong computation, and then veri-ed it locally.
We can not use this adaptive approach for constructing nonadaptive autoreductions. It seems
like -guring out the wrong computation in a nonadaptive way, requires the autoreduction to perform
the computation of the base machine itself, so the base machine has to run in polynomial time. Then
checking the computation essentially boils down to verifying the oracle answers. Using the game
characterization of the polynomial-time hierarchy along the same lines as in Theorem 4.3, we can
do this for oracles from the polynomial-time hierarchy.
Theorem 4.4 For any integer k ? 0, every 6 P
tt -complete set for \Delta P
k+1 is nonadaptively autore-
ducible.
Parallel to the adaptive case, an earlier version of this paper [6] stated Theorem 4.4 for unbounded
k, i.e., for PSPACE. However, we only get the proof to work for constant k. In Section 5, we will
see that proving Theorem 4.4 for PSPACE would separate NL from NP.
The only additional diOEculty in the proof is that in the nonadaptive setting, we do not know
which player has to perform the even rounds, and which one the odd rounds in the k-round game
underlying a query like (6). But we can just have them play both scenarios, and afterwards -gure
out the relevant run.
Proof (of Theorem 4.4)
Let A be a 6 P
tt -complete set for \Delta P
k accepted by the polynomial-time oracle Turing machine
M with oracle TQBF k . Without loss of generality there is a polynomial p and a polynomial-time
Turing machine N such that on inputs of size n, M makes exactly p(n) oracle queries q, all of the
where q has length p 2 (n). Let q(x; i) denote the i-th oracle query of M TQBF k on input x. Note that
k .
g. The set Q belongs to \Delta P
, so there is a 6 P
-reduction RQ
from Q to A.
If for a given input x, R A[fxg
Q and R Anfxg
Q agree on hx; ji for every 1 6 j 6 p(jxj), we are home:
We can simulate the base machine M using R A[fxg
as the answer to the j-th oracle query.
Otherwise, we will make use of the following functions computable in \Delta P
corresponding
oracle Turing machines R j 1
tt -reductions to A, and functions
. As in the proof of Theorem 4.3, we de-ne j ' and y ' inductively
k. They are de-ned for inputs x such that there is a smallest 1 6 i 6 p(jxj)
for which R Anfxg
ii). The value of j ' (x) equals the lexicographically least
we set j ' string does not exist. The right-hand side of (11) is 1 ioe y ' is existentially
quanti-ed in (10).
R A[fxg
R Anfxg
The condition on the right-hand side of (12) means that we use the hypothesis x 2 A to compute
y ' (x) from R j ' in case:
ffl either y ' is existentially quanti-ed in (10) and the assumption x 2 A leads to claiming that
ffl or else y ' is universally quanti-ed and the assumption x 2 A leads to claiming that (10) fails.
The intuitive meaning of the functions j ' and the reductions R j ' is similar to in the proof
of Theorem 4.3: They capture the moves during the '-th round of the game underlying (10) for
i). The function j ' encapsulates an optimal move during round ' if it exists, and the
reduction R j ' under the player's assumption regarding membership of x to A, produces the actual
move in that round. The condition on the right-hand side of (12) guarantees the correct alternation
of rounds. We refer to the proof of Theorem 4.3 for more intuition.
Consider the algorithm in Figure 4. Note that the only queries to A the algorithm in Figure 4
if R Anfxg
then accept ioe M accepts x when the j-th oracle query is answered R A[fxg
else i / -rst j such that R Anfxg
accept ioe N(q; y
where q denotes the i-th query of M on input x
when the answer to the j-th oracle query is given by R A[fxg
and
R A[fxg
R Anfxg
endif

Figure

4: Nonadaptive autoreduction for the set A of Theorem 4.4 on input x
needs to make, are the queries of RQ dioeerent from x on inputs hx; ji for 1 6 j 6 p(jxj), and the
queries of R j ' dioeerent from x on input x for 1 6 ' 6 k. Since RQ and the R j ' 's are nonadaptive, it
follows that Figure 4 describes a 6 P
tt -reduction to A that does not query its own input. A similar but
simpli-ed argument as in the proof of Theorem 4.3 shows that it accepts A. So, A is nonadaptively
autoreducible. (Theorem 4.4)
Next, we consider more restricted reductions. Using a dioeerent technique, we show:
Theorem 4.5 For any complexity class C, every 6 P
2\Gammatt -complete set for C is 6 P
2\Gammatt -autoreducible,
provided C is closed under exponential-time reductions that only ask one query which is smaller in
length.
In particular, Theorem 4.5 applies to In view of Theorems
3.1 and 3.3, this implies that Theorems 3.1, 3.3, and 4.5 are optimal.
The proof exploits the ability of EXP to simulate all polynomial-time reductions to construct
an auxiliary set D within C such that any 6 P
2\Gammatt -reductions of D to some -xed complete set A has
a property that induces an autoreduction on A.
Proof (of Theorem 4.5)
be a standard enumeration of 6 P
2\Gammatt -reductions such that M i runs in time n i on
inputs of size n. Let A be a 6 P
2\Gammatt -complete set for C.
Consider the set D that only contains strings of the form h0
decided by the algorithm of Figure 5 on such an input. Except for deciding A(x), the algorithm runs
case truth-table of M i on input h0 i ; xi with the truth-value of query x set to A(x)
constant:
rejects
of the form iy 62 Aj:
accept ioe x 62 A
otherwise:
accept ioe x 2 A
endcase

Figure

5: Algorithm for the set D of Theorem 4.5 on input h0
in exponential time. Therefore, under the given conditions on C, there is a 6 P
-reduction
M j from D to A.
The construction of D diagonalizes against every 6 P
-reduction M i of D to A whose truth-table
on input h0 would become constant once we -lled in the membership bit for x. Therefore,
for every input x, one of the following cases holds for the truth-table of M j on input h0
ffl The reduced truth-table is of the form iy 2 Aj with y 6= x.
ffl The reduced truth-table is of the form iy 62 Aj with y 6= x.
ffl The truth-table depends on the membership to A of 2 strings dioeerent from x.
Then M A
j does not query x on input h0 j ; xi, and accepts ioe x 2 A.
The above analysis shows that the algorithm of Figure 6 describes a 6 P
2\Gammatt -reduction of A.
then accept ioe M A
accepts
else
y / unique element of QM j
accept ioe y 2 A
endif

Figure

Autoreduction constructed in the proof of Theorem 4.5
(Theorem 4.5)
4.3 Probabilistic and Nonuniform Autoreductions
The previous results in this section trivially imply that the 6 P
T -complete sets for the \Delta-levels of
the exponential-time hierarchy are probabilistically autoreducible, and the 6 P
tt -complete sets for
the \Delta-levels of the polynomial-time hierarchy are probabilistically nonadaptively autoreducible.
Randomness allows us the prove more in the nonadaptive case.
First, we can establish Theorem 4.4 for EXP:
Theorem 4.6 Let f be a constructible function. Every 6 P
f(n)\Gammatt -complete set for EXP is probabilistically
O(f(n))\Gammatt -autoreducible. In particular, every 6 P
tt -complete set for EXP is probabilistically
nonadaptively autoreducible.
Proof (of Theorem 4.6)
Let A be a 6 P
f(n)\Gammatt -complete set for EXP. We will apply the PCP Theorem for EXP [2] to A.
Lemma 4.7 ([2]) There is a constant k such that for any set A 2 EXP, there is a polynomial-time
Turing machine V and a polynomial p such that for any input x:
ffl If x 2 A, then there exists a proof oracle - such that
Pr
ffl If x 62 A, then for any proof oracle -
Pr
Moreover, V never makes more than k proof oracle queries, and there is a proof oracle ~ - 2 EXP
independent of x such that (13) holds for
- in case x 2 A.
Translating Lemma 4.7 into our terminology, we obtain:
Lemma 4.8 There is a constant k such that for any set A 2 EXP, there is a probabilistic 6 P
reduction N , and a set B 2 EXP such that for any input x:
ffl If x 2 A, then N B (x) always accepts.
ffl If x 62 A, then for any oracle C, N C (x) accepts with probability at most 1
3 .
Let R be a 6 P
f(n)\Gammatt -reduction of B to A, and consider the probabilistic reduction M A that on input
runs N on input x with oracle R A[fxg . M A is a probabilistic 6 P
k \Deltaf (n)\Gammatt -reduction to A that never
queries its own input. The following shows it de-nes a reduction from A:
accepts.
ffl If x 62 A, then for accepts with probability at most 1(Theorem 4.6)
Note that Theorem 4.6 makes it plausible why we did not manage to scale down Theorem 3.2
by one exponent to EXPSPACE in the nonadaptive setting, as we were able to do for our other
results in Section 3 when going from the adaptive to the nonadaptive case: This would separate
EXP from EXPSPACE.
We suggest the extension of Theorem 4.6 to the \Delta-levels of the exponential-time hierarchy as
an interesting problem for further research.
Second, Theorem 4.4 also holds for NP:
Theorem 4.9 All 6 P
tt -complete sets for NP are probabilistically nonadaptively autoreducible.
Proof (of Theorem 4.9)
Fix a 6 P
tt -complete set A for NP. Let RA denote a length nondecreasing 6 P
m -reduction of A to SAT.
De-ne the set
is a Boolean formula with, say m variables and 9 a
there is a 6 P
-reduction RW from W to A.
We will use the following probabilistic algorithm by Valiant and Vazirani [18]:
Lemma 4.10 ([18]) There exists a polynomial-time probabilistic Turing machine N that on input
a Boolean formula ' with n variables, outputs another quanti-er
such
ffl If ' is satis-able, then with probability at least 1
4n , OE has a unique satisfying assignment.
ffl If ' is not satis-able, then OE is never satis-able.
Now consider the following algorithm for A: On input x, run N on input RA (x), yielding a
Boolean formula OE with, say m variables, and it accepts ioe
OE(R A[fxg
evaluates to true. Note that this algorithm describes a probabilistic 6 P
tt -reduction to A that never
queries its own input. Moreover:
ffl If x 2 A, then with probability at least 1
, the Valiant-Vazirani algorithm N produces a
Boolean formula OE with a unique satisfying assignment ~ a OE . In that case, the assignment we
use (R A[fxg
we accept x.
ffl If x 62 A, any Boolean formula OE which N produces has no satisfying assignment, so we always
reject x.
Executing \Theta(n) independent runs of this algorithm, and accepting ioe any of them accepts, yields a
probabilistic nonadaptive autoreduction for A. (Theorem 4.9)
So, for probabilistic autoreductions, we get similar results as for deterministic ones: Low end
complexity classes turn out to have the property that their complete sets are autoreducible, whereas
high end complexity classes do not. As we will see in more detail in the next section, this structural
dioeerence yields separations.
If we allow nonuniformity, the situation changes dramatically. Since probabilistic autoreducibil-
ity implies nonuniform autoreducibility [5], all our positive results for small complexity classes carry
over to the nonuniform setting. But, as we will see next, the negative results do not, because also
the complete sets for large complexity classes become autoreducible, both in the adaptive and in the
nonadaptive case. So, uniformity is crucial for separating complexity classes using autoreducibility,
and the Razborov-Rudich result [14] does not apply.
Feigenbaum and Fortnow [7] de-ne the following concept of #P-robustness, of which we also
consider the nonadaptive variant.
De-nition 4.1 A set A is #P-robust if #P A ' FP A ; A is nonadaptively #P-robust if #P A
FP A
tt .
Nonadaptive #P-robustness implies #P-robustness. For the usual deterministic and nondeterministic
complexity classes containing PSPACE, all 6 P
T -complete sets are #P-robust. For the
deterministic classes containing PSPACE, it is also true that the 6 P
tt -complete sets are nonadaptively
#P-robust.
The following connection with nonuniform autoreducibility holds:
Theorem 4.11 All #P-robust sets are nonuniformly autoreducible. All nonadaptively #P-robust
sets are nonuniformly nonadaptively autoreducible.
Proof
Feigenbaum and Fortnow [7] show that every #P-robust language is random-self-reducible. Beigel
and Feigenbaum [5] prove that every random-self-reducible set is nonuniformly autoreducible (or
iweakly coherentj as they call it). Their proofs carry over to the nonadaptive setting.
It follows that the 6 P
tt -complete sets for the usual deterministic complexity classes containing
PSPACE are all nonuniformly nonadaptively autoreducible. The same holds for adaptive reductions,
in which case the property is also true of nondeterministic complexity classes containing PSPACE.
In particular, we get the following:
Corollary 4.12 All 6 P
T -complete sets for NEXP, EXPSPACE, EEXP, NEEXP, EEXPSPACE,
. are nonuniformly autoreducible. All 6 P
tt -complete sets for PSPACE, EXP, EXPSPACE, . are
nonuniformly nonadaptively autoreducible.
5 Separation Results
In this section, we will see how we can use the structural property of all complete sets being
autoreducible to separate complexity classes. Based on the results of Sections 3 and 4, we only
get separations that were already known: EXPH 6= EEXPSPACE (by Theorems 4.3 and 3.1),
Theorems 4.6 and 3.2), and PH 6= EXPSPACE (by Theorems 4.4 and
3.3, and also by scaling down EXPH 6= EEXPSPACE). However, settling the question for certain
other classes, would yield impressive new separations.
We summarize the implications in Figure 7.
Theorem 5.1 In Figure 7, a positive answer to a question from the -rst column, implies the separation
in the second column, and a negative answer, the separation in the third column.
question yes no
Are all 6 P
T -complete sets for EXPSPACE autoreducible? NL 6= NP PH 6= PSPACE
Are all 6 P
T -complete sets for EEXP autoreducible?
Are all 6 P
tt -complete sets for PSPACE 6 P
Are all 6 P
tt -complete sets for EXP 6 P
Are all 6 P
tt -complete sets for EXPSPACE
probabilistically 6 P

Figure

7: Separation results using autoreducibility
Most of the entries in Figure 7 follow directly from the results of the previous sections. In order to
-nish the table, we use the next lemma:
Lemma 5.2 If NL, we can decide the validity of QBF-formulae of size t and with ff alternations
on a deterministic Turing machine M 1 in time t O(c ff ) and on a nondeterministic Turing
machine M 2 in space O(c ff log t), for some constant c.
Proof (of Lemma 5.2)
by Cook's Theorem we can transform in polynomial time a \Pi 1 -formula with free
variables into an equivalent \Sigma 1 -formula with the same free variables, and vice versa. Since
we can decide the validity of \Sigma 1 -formulae in polynomial-time. Say both the transformation algorithm
T and the satis-ability algorithm S run in time n c for some constant c.
Let OE be a QBF-formula of size t with ff alternations. Consider the following algorithm for
deciding OE: Repeatedly apply the transformation T to the largest suOEx that constitutes a \Sigma 1 - or
until the whole formula becomes \Sigma 1 , and then run S on it.
This algorithm correctly decides the truth of OE. Since the number of alternations decreases by
one during every iteration, it makes at most ff calls to T , each time at most raising the length of
the formula to the power c. It follows that the algorithm runs in time t O(c ff ) .
Moreover, since padding argument shows that DTIME[-
time constructible function - . Therefore the result holds. (Lemma 5.2)
This allows us to improve Theorems 3.2 and 3.3 as follows under the hypothesis
Theorem 5.3 If there is a 6 P
2\GammaT -complete set for EXPSPACE that is not probabilistically
autoreducible. The same holds for EEXP instead of EXPSPACE.
Proof
Combine Lemma 5.2 with the probabilistic extension of Lemma 3.4 used in the proof of Theorem
3.2.
Theorem 5.4 If there is a 6 P
3\Gammatt -complete set for PSPACE that is not nonadaptively
autoreducible. The same holds for EXP instead of PSPACE.
Proof
Combine Lemma 5.2 with Lemma 3.5.
Now, we have all ingredients for establishing Figure 7:
Proof (of Theorem 5.1)
The NL 6= NP implications in the iyesj-column of Figure 7 immediately follow from Theorems 5.3
and 5.4 by contraposition.
By Theorem 3.1, a positive answer to the 2nd question in Figure 7 would yield EEXP 6=
EEXPSPACE, and by Theorem 3.3, a positive answer to the 4th question would imply EXP 6=
EXPSPACE. By padding, both translate down to P 6= PSPACE.
Similarly, by Theorem 4.3, a negative answer to the 2nd question would imply EXPH 6= EEXP,
which pads down to PH 6= EXP. A negative answer to the 4th question would yield PH 6= EXP
directly by Theorem 4.4. By the same token, a negative answer to the 1st question results
in EXPH 6= EXPSPACE and PH 6= PSPACE, and a negative answer to the 3rd question in
PSPACE. By Theorem 4.6, a negative answer to the last question implies EXP 6= EXPSPACE
and P 6= PSPACE.
We note that we can tighten all of the separations in Figure 7 a bit, because we can apply
Lemmata 3.4 and 3.5 to smaller classes than in Theorems 3.1 respectively 3.3. One improvement
along these lines that might warrant attention is that we can replace iNL 6= NPj in Figure 7 by
This is because that condition suOEces for Theorems 5.3 and
5.4, since we can strengthen Lemma 5.2 as follows:
Lemma 5.5 If coNP ' NP " NSPACE[log O(1) n], we can decide the validity of QBF-formulae
of size t and with ff alternations on a deterministic Turing machine M 1 in time t O(c ff ) and on a
nondeterministic Turing machine M 2 in space O(d ff log d t), for some constants c and d.
6 Conclusion
We have studied the question whether all complete sets are autoreducible for various complexity
classes and various reducibilities. We obtained a positive answer for lower complexity classes in
Section 4, and a negative one for higher complexity classes in Section 3. This way, we separated
these lower complexity classes from these higher ones by highlighting a structural dioeerence. The
resulting separations were not new, but we argued in Section 5 that settling the very same question
for intermediate complexity classes, would provide major new separations.
We believe that re-nements to our techniques may lead to them, and would like to end with a
few words about some thoughts in that direction.
One does not have to look at complete sets only. Let C 1 ' C 2 . Suppose we know that all
complete sets for C 2 are autoreducible. Then it suOEces to construct, e.g., along the lines of Lemma
3.4, a hard set for C 1 that is not autoreducible, in order to separate C 1 from C 2 .
As we mentioned at the end of Section 5, we can improve Theorem 3.1 a bit by applying Lemma
3.4 to smaller space-bounded classes than EEXPSPACE. We can not hope to gain much, though,
since the coding in the proof of Lemma 3.4 seems to be DSPACE[2 n fi(n)
]-complete because of the
log fi(n) -formulae of size 2 n fi(n)
involved for inputs of size n. The same holds for Theorem 3.3
and Lemma 3.5.
Generalizations of autoreducibility may allow us to push things further. For example, one could
look at k(n)-autoreducibility where k(n) bits of the set remain unknown to the querying machine.
Theorem 4.3 goes through for k(n) 2 O(log n). Perhaps one can exploit this leeway in the coding of
Lemma 3.4 and narrow the gap between the positive and negative results. As discussed in Section
5, that would yield interesting separations.
Finally, one may want to look at other properties than autoreducibility to realize Post's Program
in complexity theory. Perhaps another concept from computability theory or a more arti-cial
property can be used to separate complexity classes.

Acknowledgments

We would like to thank Manindra Agrawal and Ashish Naik for very helpful discussions. We are
also grateful to Carsten Lund and Muli Safra for answering questions regarding the PCP Theorem.
We thank the anonymous referees for their nice suggestions on how to present our results.



--R


Proof veri-cation and hardness of approximation problems


On being incoherent without being very hard.
Using autoreducibility to separate complexity classes.
On the random-self-reducibility of complete sets
The role of relativization in complexity theory.
On the computational complexity of algorithms.
Mitotic recursively enumerable sets.
Classical Recursion Theory
Computational Complexity.
Recursively enumerable sets of positive integers and their decision problems.
Natural proofs.
Recursively Enumerable Sets and Degrees.
On autoreducibility.
On autoreducibility.
NP is as easy as detecting unique solutions.
Coherent functions and program checkers.
--TR

--CTR
Christian Glaer , Mitsunori Ogihara , A. Pavan , Alan L. Selman , Liyu Zhang, Autoreducibility, mitoticity, and immunity, Journal of Computer and System Sciences, v.73 n.5, p.735-754, August, 2007
Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December  2007
complexity classes;autoreducibility;completeness;coherence