Downward Separation Fails Catastrophically for Limited Nondeterminism Classes.
The $\beta$ hierarchy consists of classes $\beta_k={\rm NP}[logkn]\subseteq {\rm NP}$.  Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the $\beta$ hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse.  For any consistent set of collapses and separations of levels of the hierarchy that respects ${\rm \cdots \subseteq {\rm NP}$, we can construct an oracle relative to which those collapses and separations hold; at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish.  To give two relatively tame examples: for any $k \geq 1$, we construct an oracle relative to which \[ {\rm \cdots \] and another oracle relative to which \[ {\rm We also construct an oracle relative to which
Introduction
. Although standard nondeterministic algorithms solve many
NP-complete problems with O(n) nondeterministic moves, there are other problems
that seem to require very different amounts of nondeterminism. For instance, clique
can be solved with only O(
n) nondeterministic moves, and Pratt's algorithm [16]
solves primality, which is not believed to be NP-complete, with O(n 2 ) nondeterministic
moves. Motivated by the different amounts of nondeterminism apparently needed
to solve problems in NP, Kintala and Fischer [9, 10, 11] defined limited nondeterminism
classes within NP, including the classes we now call the fi hierarchy. The
structural properties of the fi classes were studied further by '
Alvarez, Diaz and Toran
[1, 6]. These classes arose yet again in the work of Papadimitriou and Yannakakis [15]
on particular problems inside NP (e.g., quasigroup isomorphism can be solved with
O(log 2 n) nondeterministic moves).
Kintala and Fischer [11] defined P f(n) to be the class of languages accepted by
a nondeterministic polynomial-time bounded Turing machine that makes at most
c-ary nondeterministic moves (equivalently, O(f(n)) binary nondeterministic
moves) on inputs of length n. Being mostly interested in polylogarithmic amounts of
nondeterminism, they defined
Diaz and Toran [6] wrote fi f(n) to denote Kintala and Fischer's P f(n) and fi k
to denote PL k . Papadimitriou and Yannakakis [15] wrote NP[f(n)] to denote P f(n) .
(Their work is surveyed in [7].) We will adopt the NP[f(n)] notation of Papadimitriou
and Yannakakis, as well as the fi k notation of Diaz and Toran. To reiterate:
Definition 1.1.
ffl A language L belongs to NP[f(n)] if there exists a polynomial-time bounded
nondeterministic Turing machine that accepts L and makes O(f(n)) nondeterministic
choices on inputs of length n. (Note: NP[f(n)] ' DTIME(2 O(f(n)) ):)
ffl The fi hierarchy consists of
y Yale University, Dept. of Computer Science, P.O. Box 208285, New Haven, CT 06520-8285.
email: beigel-richard@cs.yale.edu. Research supported in part by the United States National Science
Foundation under grant CCR-8958528 and by the Netherlands Organization for Scientific Research
(NWO) under Visitors Grant B 62-403.
z University of Kentucky, Dept. of Computer Science, Lexington, KY 40506. email:
goldsmit@cs.engr.uky.edu. Research supported in part by the National Science Foundation under
grant CCR-9315354
Kintala and Fischer [11] constructed oracles that make the fi hierarchy collapse
to any desired level. That is, there is an oracle relative to which
and, for every k - 1, there is an oracle relative to which
Oracles can also make the polynomial hierarchy and the Boolean hierarchy collapse
to any desired level [12, 4]. The polynomial and Boolean hierarchies have a
very nice property: collapses translate upward. I.e., if the kth and 1)st levels are
equal, then all levels are contained in the kth [5, 4]. This is also reflected in the non-determinism
hierarchy, now known as the b hierarchy, studied by Buss and Goldsmith
[3]. The classes in the b hierarchy are defined by two parameters: the exponent of
the polynomial time bound (ignoring log factors), and the constant factor for k log n
bits of nondeterminism. This hierarchy exhibits upward collapse for both time and
k. All attempts to prove an analogous translational property for the fi hierarchy have
failed. In fact the obvious technique extends a collapse by only a constant factor in the
number of nondeterministic bits, giving one of the aforementioned upward collapses
of the b hierarchy.
Hemachandra and Jha [8] attempted to explain this failure by examining the
tally sets in the fi hierarchy. For each k, they constructed an oracle that makes
We find this explanation unsatisfactory
because it considers only tally sets.
The known behavior of relativized fi hierarchies is that fi A
1 and that fi A
A. A collapse is a statement of the form fi A
. A
separation is a statement of the form fi A
. A closure is a statement of the form
. A nonclosure is a statement of the form fi A
. A requirement is a
collapse, separation, closure, or nonclosure. We call a set of requirements consistent if
it is consistent with the known behavior of relativized fi hierarchies, as stated above,
and the standard axioms for
Given a set S of requirements let X be the union of [0; 1] and all intervals [i; j]
such that and the collapse fi A
j belongs to S. It is easy to see that S
is consistent iff the following conditions hold for all a and b such that [a;
or [b; a] the separation fi A
a 6= fi A
b does not belong to S; (2) the closure
a and the nonclosure fi A
b do not both belong to S.
For any consistent set of requirements, we construct an oracle A such that the fi
hierarchy relative to A satisfies them. For example, for each k - 0, there is an oracle
that makes fi Another oracle makes fi
We can also make distinct levels in the hierarchy be closed under complementation or
not, as long as this is consistent with the collapses (if fi A
then we cannot have
i and fi A
We prove two initial results for every k:
ffl There is an oracle that makes the first k levels of the fi hierarchy coincide,
but makes the remaining levels all distinct (Theorem 2.3).
ffl There is an oracle that makes the first k levels of the fi hierarchy coincide,
the 1)st level different from the kth, and the remaining levels all equal
(Theorem 2.5).
The techniques from these two constructions can be combined to get any consistent
finite or infinite set of collapses and separations. To collapse fi k into fi j (for
DOWNWARD SEPARATION FAILS FOR fi HIERARCHY 3
k ? j), we code a complete set for fi k into fi j . The same coding techniques can also
code fi i into fi i , for any i's we wish, as long as this doesn't violate any collapses. (If
fi k is collapsed to fi j , then either both or neither will be closed under complement.)
Finally, in Section 3, we extend our results to fi r for real r - 0.
One theme in complexity theory is to ask whether contains any easy sets
(assuming P 6= NP). The answer to the question above depends on the definition of
"easy." Ladner [14] showed that if P 6= NP then contains an incomplete set.
On the other hand, there are oracles relative to which P 6= NP, but contains
(a) no tally sets [13] or (b) no sets in co-NP [2]. It is unknown whether the assumption
implies that contains a set in DTIME(n polylog ); a positive answer
would improve many constructions in the literature. As a step toward understanding
that question, we construct an oracle relative to which P 6= NP but contains
no set in the fi hierarchy (Corollary 2.2).
2. Limited Nondeterminism Hierarchies. The construction below gives almost
all the techniques used in subsequent theorems.
Theorem 2.1. Let g 0 and g 1 be polynomial-time computable monotone increasing
functions such that log n 2 o(g 1 (n)) and g 0 (n) 2 n O(1) . If g 0 (n O(1)
there exists an oracle A such that P (and in fact
there is a tally set in (NP[g 1 (n)]) A \Gamma (NP[g 0 (n)]) A ).
Proof. Let C accepts x within s steps with oracle
A, making at most g 0 (jxj) nondeterministic choicesg. Then C A is - p
m -complete for
for every A. Let p(n) be the polynomial time bound for some NP[g 0 (n)]
oracle Turing machine recognizing C () .
Let D A]g. Note that D A 2 NP[g 1 (n)] A .
The construction consists of coding C A into A in a polynomial-time recoverable
manner, making (NP[g 0 (n)]) A ' P A , while diagonalizing, i.e, guaranteeing that no
machine recognizes the set D A , so P A 6= (NP[g 1 (n)]) A .
At the end of the construction, we will have
We refer to all strings beginning with 1 as coding strings. We refer to all strings
beginning with 0 as diagonalizing strings.
Assume that P () is enumerated by Turing machines P (), P ()
runs
in time bounded by n i for all i, and for sufficiently large n.
The construction proceeds in stages. At the end of stage s, A is decided for all
strings of length up to n s , and D A is extended so that P A
s does not recognize D A . The
stage consists of one diagonalization, which determines n s , and continued encoding of
C A .
At stage s, choose n ? n s\Gamma1 such that n is a power of 2, the running time of P ()
s
on inputs of length n is at most n s , and n satisfies an inequality to be specified below
that is to be specified below that is true for almost all n. Let . The value of
depends only on oracle strings of length
coding strings of length -
A up to length ' \Gamma 1.
In order to diagonalize, P A
s (x) must be calculated. But that computation may
query coding strings that code computations of C A that are not yet decided, because
those computations in turn rely on strings for which A is not yet decided. Those strings
in turn may depend on other coding strings. Any diagonalizing strings that do not
4 R. BEIGEL AND J. GOLDSMITH
already belong to A and are queried by P A
s (x), or by the computation corresponding
to a coding string that P A
s (x) queries, or in the computation corresponding to a coding
string that one of those computations queries, or so on, are restrained from A. We
claim that there are more potential witnesses for x to be in D A than there are possible
queries in such a cascade of queries, so deciding P A
s (x) does not restrict our decision
about D A (x).
Because of the encoding of C A , a coding string z codes a computation that depends
only on strings of length bounded by
jzj. C A (w) directly depends on at most
p(jwj)2 g0 (jwj) of these shorter strings.
A computation of P A
s (x) may query no more than n s strings, each of length
bounded by n s . Each of these strings may code a computation on a string of length
at most n s=2 . Each of these computations depends on at most p(n s=2 )2 g0 (n s=2 ) strings,
each of which depends on at most p(n s=4 )2 g0 (n s=4 ) strings, etc.
This recursion can be cut off at strings of length ' \Gamma 1, because A is already
determined up to that length. The total number of queries needed to decide P A
s (x) is
bounded by n s times the product of all the terms above of the form p(n s=2 i
There are at most log log n s \Gamma log log log log n s \Gamma log log log s such terms,
and each of them is bounded by p(n s )2 g0 (n s Therefore the total number
of queries on which P A
s (x) depends is n s 2 O(log(s)g0 (n s )) , which is less than 2 g1 (n) for
sufficiently large n. (The inequality that n must satisfy is n s (p(n s )2 g0 (n s )
Thus there remains an unrestrained diagonalizing string of length ', which we put
into A if P A
s (x) rejects x. That is, we set D A
s (x), adding a string 0xy
to A if necessary. Thus, for each s, we can guarantee that P A
s does not accept D A ,
so
A , this shows that (NP[g 1 (n)]) A 6= P A . Since
is complete for (NP[g 0 (n)]) A , this shows that (NP[g 0 (n)]) A ' P A .
We complete stage s by letting n finishing the coding of any
C A (w) that was begun or queried in this stage.
The preceding theorem is tight because if
(even if we restrict to binary nondeterministic moves) via a relativizable proof. (Pre-
viously, Sanchis [17] had observed that if
Because the classes are separated by tally sets, we also separate the exponential-time
versions of these classes (see [8] for elaboration of this).
Corollary 2.2. There is an oracle relative to which
Proof. Let
and in the previous theorem. Then for
all k, fi A
Theorem 2.3. Let g(\Delta; \Delta) be a polynomial-time computable, monotone increasing
(in both variables) function with log
there exists an oracle A such that
(and in
fact there is a tally set in (NP[g(n; 2i for each i).
(In this theorem, we ignore the relationship between NP[g(n;
NP[g(n; 2i)]. We will take that up in the next theorem.) The only difference between
this construction and the previous one is that there are infinitely many diag-
onalizations going on. At stage we guarantee that the eth machine for
(NP[g(n; 2i)]) A does not accept the diagonal set D A
. Thus,
. The counting argument for this construction
is identical to that in the proof of Theorem 2.1.
DOWNWARD SEPARATION FAILS FOR fi HIERARCHY 5
Corollary 2.4. For any k, there is an oracle relative to which
Proof. Let g(n; in the preceding theorem.
Theorem 2.5. Let g 0 and g 1 be polynomial-time computable monotone increasing
functions such that log n 2 o(g 1 (n)) and g 0 (n) 2 n O(1) . If g 0 (n O(1)
there exists an oracle A such that
(and in fact there is a tally set in (NP[g 1 (n)]) A \Gamma (NP[g 0 (n)]) A ).
Sketch. In this construction, we do two encodings and one diagonalization. In addition
to coding C A
into P, we also code E A , a generic - p
m -complete set for PSPACE,
into A. accepts x using at most s tape squares with
oracle Ag, where we also count the space used on the oracle tape.) At the end of the
construction, we have
(If one prefers binary oracles, one may code 0, 1, and 2 as 00, 01, and 10.) When we
are doing a diagonalization to make P A
s (x) 6= D A (x), if a coding string for C A
k (w) is
queried, we proceed as before; if a coding string for E A (w) is queried, where jwj - jxj,
then we simply restrain that coding string from the oracle. This will not restrain all
the coding strings for E A (w), since there are 2 g1 (jwj) coding strings for E A (w); if
is the
upper bound on the total number of queries generated by the computation of P A
as in the proof of Theorem 2.1. Therefore, restraining any such coding strings queried
in the computation of P A
s (x) or in its cascade of queries can not restrain all such coding
strings, and thus can not decide E A (w). At the end of each stage, we complete all
codings begun or queried in that stage, so that it will not be changed in any subsequent
stage.
Corollary 2.6. For every k, there is an oracle relative to which
With only a slight modification of this technique, we get far more bizarre collapses.
Theorem 2.7. Let g(\Delta; \Delta) be a polynomial-time computable, monotone increasing
(in both variables) function with log n 2 o(g(n; i)) and g(n; i) 2 n O(1) for all i - 1.
there exists an oracle A such that
for all i - 0 (and in fact there is a tally set in (NP[g(n; 2i
for each i).
We include the full proof of this result, although it uses techniques mentioned
before, since this shows how all the pieces fit together.
Proof. Let C A
accepts x within s steps with oracle
A, making at most g(jxj; i) nondeterministic choicesg. Then C A
m -complete for
(NP[g(n; i)]) A for any A. Let p(n; i) be the nondeterministic time bound for some
6 R. BEIGEL AND J. GOLDSMITH
Turing machine recognizing C ()
. Without loss of generality, assume
that for all i and almost all n,
Let D A
A]g.
For convenience, define g(n;
The construction consists of coding C A
2i into (NP[g(n; 2i \Gamma 1)]) A , for each i - 0,
so (NP[g(n; 0)]) A ' P A and (NP[g(n; 2i
diagonalizing, i.e, guaranteeing that no (NP[g(n; 2i)]) A machine recognizes the set
D A
2i+1 , for any i, so (NP[g(n; 2i + 1)]) A 6' (NP[g(n; 2i)]) A for any i.
At the end of the construction, we will have x 2 C A
Assume that (NP[g(n; i)]) A is enumerated by oracle NTMs M
runs in time bounded by n e for sufficiently large n.
The construction proceeds in stages. Stage consists of some encodings
and one diagonalization, which determines n s . At the end of stage s, A is decided for
all strings of length - n s (and some further coding strings), and A has been extended
so that M A
e;2i does not recognize D A
2i+1 .
At stage s, let he; ii = s, and then choose n ? n s\Gamma1 such that n is a power of 2,
runs in time bounded by n e on inputs of length n, and n satisfies an inequality
to be specified below that is true for almost all n. Let n . The value
of D A
depends only on strings of length 1). Do all coding
involving witnesses of length less than ', and then freeze A through length ' \Gamma 1.
As before, in order to diagonalize, we will need to calculate M A
e;2i (x), which may
generate a cascade of queries. Any diagonalizing strings that do not already belong
to A and are queried in this cascade are restrained from A. But coding strings may
be queried as well. (Because we are coding nondeterministically, coding strings can
be thought of as potential witnesses to membership.) If M A
queries a potential
witness that w 2 C A
2j (w) has not yet been decided, that
potential witness is restrained from A. If 2j - 2i and C A
2j (w) has not yet been
decided, then we compute C A
2j (w) recursively. We will show below that the number
of queries generated by such a cascade of queries is smaller than both of the following
bounds: (1) the number of potential witnesses for w 2 C A
2j , (2) the number of potential
. In fact, bound (1) implies bound (2) as follows. The number
of witnesses for D A
2i+1 (x) is 2 g(jxj;2i+1) , and the number of witnesses for C A
2j (w) is
. If a witness of C A
2j (w) is restrained, then jwj - jxj and 2j ? 2I . Thus
by monotonicity of g, g(jwj;
Thus, restraining potential witnesses as described does not impede any encodings
or restrict our decision about D 2i+1 (x), or those C A
2j (w) for which we restrict coding
strings. (We don't have to worry about what happens to potential witnesses for
2j at a later stage, because any affected codings, i.e., C A
2j (w), will be completed
at this stage; later diagonalizations will not affect them.)
Now we show that there are more potential witnesses for x 2 D A
2i+1 than there are
possible queries in such a cascade of queries. Because of how we encode C A
k , a coding
string z codes a computation that depends on strings of length bounded by
jzj. For
(w) depends on at most p(jwj; k)2
these shorter strings.
e;2i (x) has at most 2 g(n;2i) computations, and each of those computations may
query no more than n e strings, each of length bounded by n e . Each such string may
code a computation C A
e , but we only need to expand that compu-
DOWNWARD SEPARATION FAILS FOR fi HIERARCHY 7
tation if 2j - 2i. Each of these computations depends on at most p(n e=2 ; 2i)2 g(n e=2 ;2i)
strings, each of which depends on at most p(n e=4 ; 2i)2 g(n e=4 ;2i) strings, etc. As be-
fore, the total number of queries needed to decide M A
e;i (x) is bounded by the product
of log e - log s terms, each of which is 2 o(g(n;2i+1)) . Therefore the total number of
queries on which M A
depends is 2 o(g(n;2i+1)) , which is less than 2 g(n;2i+1) for
sufficiently large n.
Thus there remains an unrestrained diagonalizing string of length ', which we
put into A if and only if M A
rejects x. That is, we set D A
adding a string 0xy to A if necessary. Thus, for each s, we can guarantee that M A
does not accept D A
this shows that (NP[g(n; 2i
Since C A
2i is complete for (NP[g(n; 2i)]) A , our encoding guarantees that
Corollary 2.8. There is an oracle relative to which, for each k, fi
fi 2k+2 .
Corollary 2.9. For any consistent pattern of collapses and separations of the
k 's, there is an oracle relative to which that pattern holds.
Notice that if the set of collapses is not recursive, then the oracle will also be
non-recursive.
In addition to collapsing or separating fi j and fi k , we can code co-fi k into fi k -
or separate the two. This involves some additional argument.
Theorem 2.10. Let g(\Delta; \Delta) be a polynomial-time computable, monotone increasing
(in both variables) function with log n 2 o(g(n; i)) and g(n; i) 2 n O(1) for all
there exists an oracle
A such that P
(and in fact there
are tally sets in (NP[g(n; 2i A and in (NP[g(n; 2i
for each i).
Sketch. For convenience, we will separate (NP[g(n; 2i+1)]) A from (co-NP[g(n; 2i
rather than (NP[g(n; 2i 2)]) A from (co-NP[g(n; 2i given the other re-
quirements, this is equivalent. In order to separate (NP[g(n; 2i 1)]) A from
we use the set D A
2i+1 in (NP[g(n; 2i
that D A
. Most of this construction is identical to that
of Theorem 2.7, except that we interleave an extra diagonalization into the construc-
tion; the codings and diagonalizations are analogous to earlier constructions, and the
counting argument is identical.
We code complete sets C A
2i for (NP[g(n; 2i)]) A into (NP[g(n; 2i \Gamma 1)]) A , and diagonalize
so that no (NP[g(n; 2i)]) A machine recognizes D A
(Thus D A
does double duty: during even stages, it diagonalizes against
during odd stages, against (co-NP[g(n; 2i
To guarantee that D A
2i+1 is not in (co-NP[g(n; 2i , we make sure that, for
each e, the e th machine for (NP[g(n; 2i does not recognize D A
. This holds
if and only if there is some x such that D A
e;2i+1 (x). This diagonalization
differs from earlier ones only when M A
queries a witness for x 2 D A
2i+1 . As
before, if M A
queries a coding string for some computation of C A
2j (w) where
then we can safely restrain the coding string. (If
may exclude w from D A
2i+1 , but that doesn't matter. As
long as D A
e;2i+1 (x), we don't care what happens to D A
2i+1 for other strings
8 R. BEIGEL AND J. GOLDSMITH
of lengths between n s\Gamma1 and n s , where then we retrace the
computation, as before.
If M A
queries a witness for x 2 D A
2i+1 , we first restrain all such wit-
nesses, and continue. If this leads to a rejecting computation of M A
2i+1 (x), and the diagonalization is successful. If it leads to an
accepting computation, we preserve the lexicographically least accepting path for
that computation, and all of its cascade of queries. As before, the computation of
restrains at most 2 o(g(n;2i+1)) strings, so this will not restrain all the witnesses
for x 2 D A
2i+1 . Thus we can find an unrestrained witness and add it to A, so
D A
e;2i+1 (x), as desired.
Therefore, this additional set of diagonalization requirements can be interleaved
with the previously-described diagonalizations and collapses.
Theorem 2.11. Let g(\Delta; \Delta) be a polynomial-time computable, monotone increasing
(in both variables) function with log n 2 o(g(n; i)) and g(n; i) 2 n O(1) for all
there exists an oracle
A such that P
(and in fact there are tally
sets in (NP[g(n; 2i for each i).
Sketch. As before, we construct A so that no (NP[g(n; 2i)]) A machine recognizes
the set D A
2i+1 , and so that C A
In addition, in order to make
as follows:
For each i, let N A
i be an (NP[g(n; i)]) A machine recognizing C A
i in nondeterministic
time bounded by p(n; i) (regardless of the oracle). By the form of the encoding,
query any of its own coding strings. If a witness string for C A
is queried in the course of a diagonalization (NP[g(n; 2i)]) A 6= (NP[g(n; 2i
then we can retrace the computation. If 2j
we can restrain the queried witness string (for jxj sufficiently large) without deciding
C A
2j+1 (x), by the same counting argument as in previous proofs.
Thus, we can add this extra encoding, without interfering with the other collapses
and codings.
This gives us the following stronger version of Hemachandra and Jha's oracle [8].
Corollary 2.12. For each k, there is an oracle relative to which for all j,
(and the separations are witnessed by tally sets).
Combining the results (and techniques) of Theorems 2.7, 2.10, and 2.11, we get
the following very strong result.
Corollary 2.13. For any consistent set of requirements, there is an oracle
relative to which the fi hierarchy satisfies those requirements.
In constructing such an oracle, one must be careful in closing classes under com-
plement. In particular, if we close one class under complement, and separate another
from its complement, we cannot then make the two classes equal.
Corollary 2.9 implies that there are uncountably many different patterns of collapse
that can be realized in relativized worlds. If the set of requirements is recursive,
then the oracle can be made recursive, but certainly some of those patterns are realized
by only nonrecursive oracles.
DOWNWARD SEPARATION FAILS FOR fi HIERARCHY 9
3. Dense fi Hierarchies. Previously we considered fi r only when r is a natural
number. But the class (NP[log r n]) A is meaningful whenever r is a nonnegative real
number (regardless of whether r is computable). Even when we allow r to be real, we
can make the fi hierarchy obey any consistent set of requirements. For example, we
can make the fi hierarchy look like a Cantor set.
Theorem 3.1. Let X be any subset of [1; 1). There exists an oracle A such
that, for all s; t - 1, fi A
t if and only if [s; t] ' X.
Note that there may be uncountably many distinct fi t s. Because there are two
rationals between any two reals, we need only separate the distinct fi q s where q is
rational.
Proof. Without loss of generality, assume that X is a union of intervals, each containing
more than one point. Every interval in X contains a rational point; therefore
contains countably many intervals.
We will satisfy the following requirements for each maximal interval in X , depending
on its type:
log log n]
log log n]
In addition, for each rational number q in (1;
NP[log q n= log log n] 6= NP[log q n] 6= NP[log q n log log n]:
then we make P 6= NP[log n log log n] as well.
The construction is a slight modification of that in the proof of Theorem 2.7.
We perform the diagonalizations in some well-founded order, while maintaining the
codings as we go along. The only significant difference here is that the diagonalizations
are not performed in increasing order. Suppose that at some stage we are making
ae NP[b(n)] and a coding string for some NP[c(n)] computation is queried;
we restrain that string if and only if (9n)[c(n) ? b(n)] if and only if (8n)[c(n) - b(n)].
The counting argument is the same as before.
Note: we could also close each distinct fi r under complement or not, as we wish,
in the theorem above.
4. Open Problems. The class fi k is contained in NP " DTIME(2 log k n ). Our
work shows that there is no relativizing proof that We would
like to know whether
are there any easy languages in NP \Gamma P? The best we can show is that if
well-behaved function f , then
Is there an oracle relative to which this is the best possible translation of the collapse?
Does

Acknowledgments

. We are grateful to Leen Torenvliet, Andrew Klapper, and
Martin Kummer for helpful discussions, and Andrew Klapper, Bill Gasarch, and Martin
Kummer for careful proofreading of earlier drafts.



--R

"Complexity Classes With Complete Problems Between P and NP-Complete,"
Relativizations of the P
"Nondeterminism within P,"
The Boolean hierarchy I: structural properties.

Classes of bounded nondeterminism.
Limited nondeterminism SIGACT News
Defying upward and downward separation.
Computations with a restricted number of nondeterministic steps.
Computations with a restricted number of nondeterministic steps.
Refining nondeterminism in relativized polynomial-time bounded computations
Relativized polynomial hierarchies having exactly k levels.
Sparse sets in NP
On the structure of polynomial time reducibility.
On limited nondeterminism and the complexity of the V-C dimension
Every prime has a succinct certificate.
Constructing language instances based on partial information.
--TR
oracles;structural complexity theory;hierarchies;limited nondeterminism