New Collapse Consequences of NP Having Small Circuits.
We show that if a self-reducible set has polynomial-size circuits, then it is low for the probabilistic class ZPP (NP). As a consequence we get a deeper collapse of the polynomial-time hierarchy PH to ZPP(NP) under the assumption that NP has polynomial-size circuits. This improves on the well-known result in Karp and Lipton [ Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302--309] stating a collapse of PH to its second level $\Sigmap_2$ under the same assumption.  Furthermore, we derive new collapse consequences under the assumption that complexity classes like UP, FewP, and C=P have polynomial-size circuits.  Finally, we investigate the circuit-size complexity of several language classes. In particular, we show that for every fixed polynomial s, there is a set in ZPP(NP) which does not have O(s(n))-size circuits.
Introduction
. The question of whether intractable sets can be efficiently
decided by non-uniform models of computation has motivated much work in structural
complexity theory. In research from the early 1980's to the present, a variety of results
has been obtained showing that this is impossible under plausible assumptions (see,
e.g., the survey [18]). A typical model for non-uniform computations are circuit
families. In the notation of Karp and Lipton [22], sets decidable by polynomial-size
circuits are precisely the sets in P/poly, i.e., they are decidable in polynomial time
with the help of a polynomial length bounded advice function [32].
Karp and Lipton (together with Sipser) [22] proved that no NP-complete set
has polynomial size circuits (in symbols NP 6' P/poly) unless the polynomial time
hierarchy collapses to its second level. The proof given in [22] exploits a certain kind
of self-reducibility of the well-known NP-complete problem SAT. More generally, it is
shown in [8, 7] that every (Turing) self-reducible set in P/poly is low for the second
level \Sigma P
2 of the polynomial time hierarchy. Intuitively speaking, a set is low for a
relativizable complexity class if it gives no additional power when used as an oracle
for that class.
In this paper, we show that every self-reducible set in P/poly is even low for the
probabilistic class ZPP(NP), meaning that for every
oracle A, \Sigma lowness for ZPP(NP) implies lowness for \Sigma P. As
a consequence of our lowness result we get a deeper collapse of the polynomial-time
hierarchy to ZPP(NP) under the assumption that NP has polynomial-size circuits. At
Abteilung f?r Theoretische Informatik, Universit?t Ulm, Oberer Eselsberg, D-89069 Ulm, Germany
(koebler@informatik.uni-ulm.de).
y Department of Computer Science, Tokyo Institute of Technology, Meguro-ku, Tokyo 152, Japan
(watanabe@cs.titech.ac.jp). Part of this work has been done while visiting the University of Ulm
(supported in part by the guest scientific program of the University of Ulm).
J. K -
OBLER AND O. WATANABE
least in some relativized world, the new collapse level is quite close to optimal: there
is an oracle relative to which NP is contained in P/poly but PH does not collapse to
P(NP) [17, 39].
We also derive new collapse consequences from the assumption that complexity
classes like UP, FewP, and C=P have polynomial-size circuits. Furthermore, our
lowness result implies new relativizable collapses for the case that Modm P, PSPACE,
or EXP have polynomial-size circuits. As a final application, we derive new circuit-
size lower bounds. In particular, it is shown (by relativizing proof techniques) that for
every fixed polynomial s, there is a set in ZPP(NP) which does not have O(s(n))-size
circuits. This improves on the result of Kannan [21] that for every polynomial s, the
class \Sigma P
2 contains such a set. It further follows that in every relativized world,
there exist sets in the class ZPEXP(NP) that do not have polynomial-size circuits.
It should be noted that there is a non-relativizing proof for a stronger result. As a
corollary to the result in [4], which is proved by a non-relativizing technique, it is
provable that MA exp " co-MA exp (a subclass of ZPEXP(NP)) contains non P/poly
sets [12, 36].
Some explanation of how our work builds on prior techniques is in order. The
proof of our lowness result heavily uses the universal hashing technique [13, 34] and
builds on ideas from [2, 14, 24]. For the design of a zero error probabilistic algorithm
which, with the help of an NP oracle, simulates a given ZPP(NP(A)) computation
(where A is a self-reducible set in P/poly) we further make use of the newly defined
concept of half-collisions. More precisely, we show how to compute on input 0 n in
expected polynomial time a hash family H that can be used to decide all instances
of A of length up to n by a strong NP computation. The way H is used to decide
(non)membership to A is by checking whether H leads to a half-collision on certain
sets. Very recently, Bshouty, Cleve, Gavald'a, Kannan, and Tamon [11] building on
a result from [19] have shown that the class of all circuits is exactly learnable in
(randomized) expected polynomial time with equivalence queries and the aid of an
NP oracle. This immediately implies that for every set A in P/poly an advice function
can be computed in FZPP(NP(A)), i.e., by a probabilistic oracle transducer T in
expected polynomial time under an oracle in NP(A). More precisely, since the circuit
produced by the probabilistic learning algorithm of [11] depends on the outcome of
the coin flips, T computes a multi-valued advice function, i.e., on input 0 n , T accepts
with probability at least 1/2, and on every accepting path, T outputs some circuit
that correctly decides all instances of length n w.r.t. A. Using the technique in [11] we
are able to show that every self-reducible set A in P/poly even has an advice function
in FZPP(NP). Although this provides a different way to deduce the ZPP(NP) lowness
of all self-reducible sets in P/poly, we prefer to give a self-contained proof using the
"half-collision technique" that does not rely on the mentioned results in [11, 19].
The paper is organized as follows: Section 2 introduces notation and defines the
self-reducibility that we use. In Section 3 we prove the ZPP(NP) lowness of all self-
reducible sets in P/poly. In Section 4 we state the collapse consequences, and the
new circuit-size lower bounds are derived in Section 5.
2. Preliminaries and notation. All languages are over the binary alphabet
1g. As usual, we denote the lexicographic order on \Sigma   by -. The length
of a string x 2 \Sigma   is denoted by jxj. \Sigma -n (\Sigma !n ) is the set of all strings of length
at most n (resp., of length smaller than n). For a language A, A
. The cardinality of a finite set A is denoted by jAj. The characteristic
function of A is defined as otherwise. For a class
C of sets, co-C denotes the class f\Sigma   \Gamma A j A 2 Cg. To encode pairs (or tuples) of
strings we use a standard polynomial-time computable pairing function denoted by
h\Delta; \Deltai whose inverses are also computable in polynomial time. Where intent is clear
we in place of f(hx denotes the set of non-negative
integers. Throughout the paper, the base of log is 2.
The textbooks [9, 10, 25, 31, 33] can be consulted for the standard notations used
in the paper and for basic results in complexity theory. For definitions of probabilistic
complexity classes like ZPP see also [15].
An machine M is a polynomial-time nondeterministic Turing machine. We
assume that each computation path of M on a given input x either accepts, rejects, or
outputs "?". M accepts on input x, if M performs at least one accepting computation,
otherwise M rejects x. M strongly accepts (strongly rejects) x [26] if
ffl there is at least one accepting (resp., rejecting) computation path and
ffl there are no rejecting (resp., accepting) computation paths.
If M strongly accepts or strongly rejects x, M is said to perform a strong computation
on input x. An NP machine that on every input performs a strong computation is
called a strong NP machine. It is well known that exactly the sets in NP " co-NP are
accepted by strong NP machines [26].
Next we define the kind of self-reducibility that we use in this paper.
Definition 2.1. Let - be an irreflexive and transitive order relation on \Sigma   . A
sequence of strings is called a -chain (of length k) from x 0 to x k if
Relation - is called length checkable if there is a polynomial q
such that
1. for all x; y 2 \Sigma   , x - y implies jyj - q(jxj),
2. the language fhx; there is a -chain of length k from x to yg is in NP.
Definition 2.2. A set A is self-reducible, if there is a polynomial-time oracle
machine M self and a length checkable order relation - such that
on any input x, M self queries the oracle only about strings y OE x.
It is straightforward to check that the polynomially related self-reducible sets introduced
by Ko [23] as well as the length-decreasing and word-decreasing self-reducible
sets of Balc'azar [6] are self-reducible in our sense. Furthermore, it is well-known (see,
for example, [9, 6, 29]) that complexity classes like NP, \Sigma P
PSPACE, and EXP have many-one complete self-reducible sets.
Karp and Lipton [22] introduced the notion of advice functions in order to characterize
non-uniform complexity classes. A function h : N ! \Sigma   is called a polynomial-
length function if for some polynomial p and for all n - 0, p(n). For a
class C of sets, let C=poly be the class of sets A such that there is a set I 2 C and a
4 J. K -
OBLER AND O. WATANABE
polynomial-length function h such that for all n and for all x 2 \Sigma -n ,
Function h is called an advice function for A, whereas I is the corresponding interpreter
set.
In this paper we will heavily make use of the "hashing technique" which has been
very fruitful in complexity theory. Here we review some notations and facts about
hash families. We also extend the notion of "collision" by introducing the concept of
a "half-collision" which is central to our proof technique.
Sipser [34] used universal hashing, originally invented by Carter and Wegman
[13], to decide (probabilistically) whether a finite set X is large or small. A linear
function h from \Sigma m to \Sigma k is given by a Boolean (k; m)-matrix (a ij ) and maps
any string x to a string is the inner product
of the i-th row a i and x.
h be a linear hash function from \Sigma m to \Sigma k . Then
we say that x has a collision on Y w.r.t. h if there exists a string y 2 Y , different
from x, such that generally, if X is a subset of \Sigma m and H is a
family l ) of linear hash functions from \Sigma m to \Sigma k , then we say that X has
a collision on Y w.r.t. H (Collision(X; Y; H) for short) if there is some x 2 X that
has a collision on Y w.r.t. every h i in H. That is,
and for all
If X has a collision on itself w.r.t. H, we simply say that X has a collision w.r.t.
H. Next we extend the notion of "collision" in the following way. For any X and Y
family l ) of linear hash functions, we say that X has a
half-collision on Y w.r.t. H (Half-Collision(X; Y; H) for short) if there is some x 2 X
that has a collision on Y w.r.t. at least dl=2e many of the hash functions h i in H.
That is,
Half-Collision(X;
and
An important relationship between collisions and half-collisions is the following one:
If X has a collision w.r.t. H on must have a half-collision w.r.t.
H either on Y 1 or on Y 2 .
Note that the predicate Collision(X; Y; H) can be decided in NP provided that
membership in X and Y can be tested in NP. More precisely, the language fhv; Hi j
(as well as the set fhv; Hi j Half-Collision(X
to NP, if the sets X v and Y v are succinctly represented in such a way that the languages
are in NP.
We denote the set of all families l ) of l linear hash functions from
\Sigma m to \Sigma k by H(l; m; k). The following theorem is proved by a pigeon-hole argument.
It says that every sufficiently large set must have a collision w.r.t. any hash family.
Theorem 2.3. [34] For any hash family H 2 H(l; m; k) and any set X ' \Sigma m of
cardinality jXj ? l must have a collision w.r.t. H.
On the other hand, we get from the next theorem (called Coding Lemma in [34])
an upper bound on the collision probability for sufficiently small sets.
Theorem 2.4. [34] Let X ' \Sigma m be a set of cardinality at most 2 k\Gamma1 . If we
choose a hash family H uniformly at random from H(k; m; k), then the probability
that X has a collision w.r.t. H is at most 1=2.
We will also make use of the following extension of Theorem 2.4 which can be
proved along the same lines.
Theorem 2.5. Let X ' \Sigma m be a set of cardinality at most 2 k\Gammas . If we choose a
family H uniformly at random from H(l; m; k), then the probability that X has
a collision w.r.t. H is at most 2 k\Gammas(l+1) .
Gavald'a [14] extended Sipser's Coding Lemma (Theorem 2.4) to the case of a
collection C of exponentially many sets. The following theorem has a similar flavor.
Theorem 2.6. Let C be a collection of at most 2 n subsets of \Sigma m , each of which
has cardinality at most 2 k\Gammas . If we choose a hash family H uniformly at random from
then the probability that some X 2 C has a collision w.r.t. H is at most
Proof. By Theorem 2.5, we have that for every fixed X 2 C, the probability
that it has a collision w.r.t. a randomly chosen hash family H 2 H(l; m; k) is at
most 2 k\Gammas(l+1) . Hence, the probability that there exists such a set X 2 C is at most
In this paper we make use of a corresponding result for the case of half-collisions.
Theorem 2.7. Let X ' \Sigma m and let C be a collection of at most 2 n subsets of
, each of which has cardinality at most 2 k\Gammas\Gamma2 . If we choose a hash family H
uniformly at random from H(l; m; k), then the probability that X has a half-collision
on some Y 2 C w.r.t. H is at most jXj \Delta 2 n\Gammasl=2 .
Proof. For every fixed Y 2 C and every fixed x 2 X, the probability that x has
a collision on Y w.r.t. a randomly chosen h is at most 2 \Gammas\Gamma2 . Hence, the probability
that x has a collision on Y w.r.t. at least half of the functions in a randomly chosen
hash family H 2 H(l; m; k) is at most
l
l
That is, the probability that x has a half-collision on Y w.r.t. a randomly chosen hash
family H is bounded by 2 \Gammasl=2 . Hence, the probability that there exists a Y 2 C and
an x 2 X such that x has a half-collision on Y w.r.t. H is at most jXj \Delta 2 n\Gammasl=2 .
3. Lowness of self-reducible sets in P/poly. In this section, we show that every
self-reducible set A in (NP " co-NP)=poly is low for ZPP(NP). Let I 2 NP " co-NP
6 J. K -
OBLER AND O. WATANABE
be an interpreter set and h be an advice function for A. We construct a probabilistic
algorithm T and an NP oracle O having the following two properties:
a) The expected running time of T is polynomially bounded.
b) On every computation path on input 0 n , T with oracle O outputs some
information that can be used to determine the membership to A of any x
up to length n by some strong NP computation (in the sense of [26]).
Using these properties, we can prove the lowness of A for ZPP(NP) as follows: In
order to simulate any NP(A) computation, we first precompute the above mentioned
information for A (up to some length) by T O , and then by using this information,
we can simulate the NP(A) computation by some NP(NP " co-NP) computation.
Note that the precomputation (performed by T O ) can be done in ZPP(NP), and
since the remaining computation can be done in NP. Hence,
which implies further that ZPP(NP(A)) ' ZPP(ZPP(NP)) (=
ZPP(NP) [41]).
We will now make the term "information" precise. For this, we need some additional
notation. Let the self-reducibility of A be witnessed by a polynomial-time
oracle machine M self , a length checkable order relation -, and a polynomial q. We
assume that fixed polynomial p ? 0. In the following, we
fix n and consider instances of length up to q(n) as well as advice strings of length
exactly p(n).
ffl A sample is a sequence hx of pairs, where the x i 's are
instances of length up to q(n) and b
ffl For any sample Consistent(S) be the set of all
advice strings w that are consistent with S, i.e.
The cardinality of Consistent(S) is denoted by c(S).
ffl For any sample S and any instance x, let Accept(x; S) (resp., Reject(x; S))
be the set of all consistent advice strings that accept x (resp., reject x):
and
ffl Let Correct(x; S) be the set fw 2 Consistent(S) j I(x; of consistent
advice strings that decide x correctly, and let Incorrect(x; S) be the
complementary set fw 2 Consistent(S) j I(x; w) 6= A(x)g.
Note that the sets Accept(x; S) and Reject(x; S) (as well as Correct(x; S) and
Incorrect(x; S)) form a partition of the set Consistent(S), and that
The above condition b) can now be precisely stated as follows:
b) On every computation path on input 0 n , T O outputs a pair hS; Hi consisting
of a sample S and a linear hash family H such that for all x up to length
n, Consistent(S) has a half-collision w.r.t. H on Correct(x; S), but not on
Incorrect(x; S).
Once we have a pair hS; Hi satisfying condition b), we can determine whether an
instance x of length up to n is in A by simply checking whether Consistent(x; S)
has a half-collision w.r.t. H on Accept(x; S) or on Reject(x; S). Since condition b)
guarantees that the half-collision can always be found, this checking can be done by
a strong NP computation. Let us now prove our main lemma.
Lemma 3.1. For any self-reducible set A in (NP " co-NP)=poly, there exist a
probabilistic transducer T and an oracle O in NP satisfying the above two conditions.
Proof. We use the notation introduced so far. Recall that q(n) is a length bound
on the queries occuring in the self-reduction tree produced by M self on any instance of
length n and that p(n) is the advice length for the set of all instances of length up to
q(n). Let l be the polynomial defined as 1). Further, we denote
by \Sigma -n the set fy j 9x 2 \Sigma -n ; y - xg. Then it is clear that \Sigma -n ' \Sigma -n ' \Sigma -q(n) . A
description of T is given below.
input
loop
randomly from H(l(n); p(n); k),
has a collision w.r.t. H k g
if there exists an x 2 \Sigma -n such that Consistent(S) has
a half-collision on Incorrect(x; S) w.r.t. H kmax
then
use oracle O to find such a string x and to determine A(x)
else exit(loop) end
loop
output
Starting with the empty sample, T enters the main loop. During each execution
of the loop, T first randomly guesses a series of p(n) many hash families
computes the integer kmax as the maximum
p(n)g such that Consistent(S) has a collision w.r.t. H k . Notice that
by a padding trick we can assume that c(S) is always larger than 2l(n), implying that
Consistent(S) must have a collision w.r.t. H 1 . Since, in particular, Consistent(S) has
a collision w.r.t. H kmax , it follows that for every instance x 2 \Sigma -n , Consistent(S) has
a half-collision w.r.t. H kmax on either Correct(x; S) or Incorrect(x; S). If there exists
a string x 2 \Sigma -n such that Consistent(S) has a half-collision on Incorrect(x; S) w.r.t.
H kmax , then this string is added to the sample S and T continues executing the loop.
(We will describe below how T uses the NP oracle O to find x in this case.) Otherwise,
8 J. K -
OBLER AND O. WATANABE
the pair hS; H kmax i fulfills the properties stated in condition b) and T halts.
We now show that the expected running time of T is polynomially bounded. Since
the initial size of Consistent(S) is 2 p(n) , and since Consistent(S) never becomes empty,
it suffices to prove that for some polynomial r, T eliminates in each single execution
of the main loop with probability at least 1=r(n) at least an 1=r(n)-fraction of the
circuits in Consistent(S). In fact, we will show that each single extension of S by a
reduces the size of Consistent(S) with probability at least by a
factor smaller than can only perform more than 2 7 l(n)p(n) loop
iterations, if during some iteration of the main loop T extends S by a pair hx; A(x)i
which does not shrink the size of Consistent(S) by a factor smaller than
the probability for this event is bounded by 2 7 l(n)p(n)
Let S be a sample and let kmax be the corresponding integer as determined by T
during some specific execution of the loop. We first derive a lower bound for kmax .
be the smallest integer k - 1 such that c(S) - l(n)2 k+1 . Since either
p(n) or Consistent(S) does not have a collision w.r.t. the hash family H kmax
1), we have (using Theorem 2.3) that c(S) - l(n)2 kmax +1 . Hence,
Since T expands S only by strings x 2 \Sigma -n such that Consistent(S) has a
half-collision on Incorrect(x; S) w.r.t. H kmax , and since Consistent(S#hx;
the probability that the size of Consistent(S) does
not decrease by a factor smaller than bounded by the probability that,
w.r.t. H kmax , Consistent(S) has a half-collision on some set Incorrect(x; S) of size at
most c(S)=2 7 l(n). Let
it follows from
Theorem 2.7 that the probability of Consistent(S) having a half-collision on some
w.r.t. a uniformly at random chosen hash family H 2 H(l(n);
at most
Thus the probability that for some k - 0, Consistent(S) has a half-collision w.r.t.
H k0+k on some set Incorrect(x; S) which is of size at most c(S)=2 7 l(n) is bounded by
We finally show how T determines an instance x 2 \Sigma -n (if it exists) such that
Consistent(S) has a half-collision on Incorrect(x; S) w.r.t. H kmax . Intuitively, we use
the self-reducibility of A to test the "correctness" w.r.t. A of the "program" hS; H kmax i,
where we say that
ffl a pair hS; Hi accepts an instance x if Consistent(S) has a half-collision on
ffl hS; Hi rejects x if Consistent(S) has a half-collision on Reject(x; S) w.r.t. H.
Notice that an (incorrect) program might accept and at the same time reject an
instance. The main idea to find out whether hS; H kmax i is incorrect on some instance
(meaning that w.r.t. H kmax Consistent(S) has a half-collision on
Incorrect(x; S)) is to test whether the program hS; H kmax i is in accordance with the
output of M self when the oracle queries of M self are answered according to the program
To be more precise, consider the NP set
Hi j there is a computation path - of M self on input z fulfilling
the following properties:
- if a query q is answered 'yes', then hS; Hi accepts q,
- if a query q is answered 'no', then hS; Hi rejects q,
if - is accepting, then hS; Hi rejects z, and
if - is rejecting, then hS; Hi accepts z g.
Then, as shown by the next claim, the correctness of hS; H kmax i on an instance z can
be decided by asking whether hz; belongs to B, provided that hS; H kmax i is
correct on all potential queries of M self on input z.
Claim. Assume that hS; H kmax i is correct on all y OE z. Then hS; H kmax i is
incorrect on z if and only if hz; belongs to B.
Proof. Using the fact that for every instance x 2 \Sigma -n , Consistent(S) has a half-
collision w.r.t. H kmax on either Correct(x; S) or Incorrect(x; S), it is easy to see that if
is incorrect on z, then the computation path - followed by M self (z) under
oracle A witnesses hz; B. For the converse, assume that hz;
belongs to B and let - be a computation path witnessing this fact. Note that all
queries q on - are answered correctly w.r.t. A, since otherwise hS; H kmax i were incorrect
on q OE z. Hence, - is the path followed by M self (z) under oracle A and therefore
decides z correctly. On the other hand, since - witnesses hz;
indeed is incorrect on z.
Now we can define the oracle set O as C \Phi D, where
Hi j there is a -chain of length (at least) k from some
string y 2 \Sigma -n to some string z - x such that hz;
and
Hi j there is an accepting computation path - of M self on input
x such that any query q is only answered 'yes' (`no') if Consistent(S)
has a half-collision on Accept(q; S) (resp., Reject(q; S)) w.r.t. H g.
Note that the proof of the claim above also shows that for any z 2 \Sigma -n such
that is correct on all y OE z, z 2 A if and only if hz;
to D. Now we can complete the description of T . T first asks whether the
string belongs to C. It is clear that a negative answer implies
that is correct on \Sigma -n . Otherwise, by asking queries of the form
computes by binary search i max as the maximum value
belongs to C (a similar idea is used
OBLER AND O. WATANABE
input
loop
randomly from H(l(n); p(n); k),
has a collision w.r.t. H k g
if
else exit(loop) end
loop
output
in [27]). Knowing i determines the lexicographically smallest string xmin
such that h0 is in C. Since hq; holds for all
instances q OE xmin , it follows inductively from the claim that hS; H kmax i is correct on
all q OE xmin . Hence, must be incorrect on xmin , and furthermore, T can
determine the membership of xmin to A by asking whether the string hx min ;
belongs to D.
Theorem 3.2. Every self-reducible set A in the class (NP " co-NP)=poly is low
for ZPP(NP).
Proof. We first show that NP(A) ' ZPP(NP). Let L be a set in NP(A), and let
M be a deterministic polynomial-time oracle machine such that for some polynomial
t,
Let s(n) be a polynomial bounding the length of all oracle queries of M on some
input hx; yi where x is of length n. Then L can be accepted by a probabilistic oracle
machine N using the following NP oracle
O Hi j there is a y 2 \Sigma t(jxj) such that M on input hx; yi has an
accepting path - on which each query q is answered 'yes' (`no') only
if Consistent(S) has a half-collision on Accept(q; S) (resp., Reject(q; S))
w.r.t. H g.
Here is how N accepts L. On input x, N first simulates T on input 0 s(jxj) to compute
a pair hS; H kmax i as described above (T asks questions to some NP oracle O). Then
N asks the query hx; O 0 to find out whether x is in L.
This proves that NP(A) ' ZPP(NP). Since via a proof
that relativizes, it follows that ZPP(NP(A)) is also contained in ZPP(NP), showing
that A is low for ZPP(NP).
4. Collapse consequences. As a direct consequence of Theorem 3.2 we get an
improvement of Karp, Lipton, and Sipser's result [22] that NP is not contained in
P/poly unless the polynomial-time hierarchy collapses to \Sigma P
.
Corollary 4.1. If NP is contained in (NP " co-NP)=poly then the polynomial-time
hierarchy collapses to ZPP(NP).
Proof. Since the NP-complete set SAT is self-reducible, the assumption that NP
is contained in (NP " co-NP)=poly implies that SAT is low for ZPP(NP), and hence
the polynomial-time hierarchy collapses to ZPP(NP).
The collapse of the polynomial-time hierarchy deduced in Corollary 4.1 is quite
close to optimal, at least in some relativized world [17, 39]: there is an oracle relative to
which NP is contained in P/poly but the polynomial-time hierarchy does not collapse
to P(NP).
In the rest of this section we report some other interesting collapses which can be
easily derived using (by now) standard techniques, and which have also been pointed
out independently by several researchers to the second author. First, it is straightforward
to check that Theorem 3.2 relativizes: For any oracle B, if A is a self-reducible
set in the class (NP(B) " co-NP(B))=poly, then NP(A) is contained in ZPP(NP(B)).
Consequently, Theorem 3.2 generalizes to the following result.
Theorem 4.2. If A is a self-reducible set in the class (\Sigma P
)=poly, then
As a direct consequence of Theorem 4.2 we get an improvement of results in
[1, 20] stating (for
k is not contained in (\Sigma P
)=poly unless the
polynomial-time hierarchy collapses to \Sigma P
.
Corollary 4.3. Let k - 1. If \Sigma P
k is contained in (\Sigma P
)=poly, then the
polynomial-time hierarchy collapses to ZPP(\Sigma P
Proof. Since \Sigma P
contains complete self-reducible languages, the assumption that
k is contained in (\Sigma P
)=poly implies that \Sigma P
Yap [40] proved that \Pi P
k is not contained in \Sigma P
=poly unless the polynomial-time
hierarchy collapses to \Sigma P
k+2 . As a further consequence of Theorem 4.2 we get the
following improvement of Yap's result.
Corollary 4.4. For k - 1, if \Pi P
=poly, then
Proof. The assumption that \Pi P
k is contained in \Sigma P
=poly implies that \Sigma P
k+1 is
contained in \Sigma P
=poly ' (\Sigma P
)=poly. Hence we can apply Corollary 4.3.
As corollaries to Theorem 4.2, we also have similar collapse results for many other
complexity classes. What follows are some typical examples.
Corollary 4.5. For K 2 co-NP)=poly then K is low
for ZPP(NP).
Proof. It is well-known that for every set A in UP (FewP), the left set of A [30] is
word-decreasing self-reducible and in UP (resp., FewP). Thus, under the assumption
that UP ' (NP " co-NP)=poly (resp., FewP ' (NP " co-NP)=poly) it follows by
Theorem 3.2 that the left set of A (and since A is polynomial-time many-one reducible
to its left set, also is low for ZPP(NP).
Corollary 4.6. For every k - 1, if C=P ' (\Sigma P
)=poly then
Proof. First, since C=P has complete word-decreasing self-reducible languages
)=poly implies C=P ' ZPP(\Sigma P
OBLER AND O. WATANABE
)=poly implies PH ' (\Sigma P
k )=poly and therefore
PH collapses to ZPP(\Sigma P
k ) by Corollary 4.3. Finally, since C=P(PH) ' BPP(C= P)
[37], it follows that C=P(PH) ' PH, and since
[38]), we get inductively that CH ' PH (' ZPP(\Sigma P
Corollary 4.7. Let K 2. If for some k - 1,
)=poly, then K ' PH and PH collapses to ZPP(\Sigma P
Proof. The proof for K 2 fEXP;PSPACEg is immediate from Theorem 4.2 since
PSPACE has complete (length-decreasing) self-reducible languages, and since EXP
has complete (word-decreasing) self-reducible languages [6].
The proof for K 2 is analogous to the one of Corollary 4.6
using the fact that ModmP has complete word-decreasing self-reducible languages
[29], and that PH ' BPP(Modm P) [37, 35].
Since our proof technique is relativizable, the above results hold for every relativized
world. On the other hand, it is known that for some classes stronger collapse
consequences can be obtained by using non-relativizable arguments.
Theorem 4.8. [28, 4, 3] For K 2 fPP; ModmP;PSPACE;EXPg, if K ' P/poly
then K ' MA.
Harry Buhrman pointed out to us that Corollary 4.7 can also be derived from
Theorem 4.8.
5. Circuit complexity. Kannan [21] proved that for every fixed polynomial s,
there is a set in \Sigma P
which cannot be decided by circuits of size s(n). Using a
padding argument, he obtained the existence of sets in NEXP(NP) " co-NEXP(NP)
not having polynomial-size circuits.
Theorem 5.1. [21]
1. For every polynomial s, there is a set in \Sigma P
2 that does not have circuits
of size s(n).
2. For every increasing time-constructible super-polynomial function f(n), there
is a set in NTIME[f(n)](NP)"co-NTIME[f(n)](NP) that does not have polynomial
size circuits.
As an application of our results in Section 3, we can improve Kannan's results
in every relativized world from the class \Sigma P
2 to ZPP(NP), and from the class
" co-NTIME[f(n)](NP) to ZPTIME[f(n)](NP), respectively. Here
ZPTIME[f(n)](NP) denotes the class of all sets that are accepted by some zero error
probabilistic machine in expected running time O(f(n)) relative to some NP oracle.
Note that for all sets in the class P/poly we may fix the interpreter set to some
appropriate one in P. Let I univ denote such a fixed interpreter set. Furthermore,
P/poly remains the same class, if we relax the notion of an advice function h (w.r.t.
I univ ) as follows: For every x, I univ (x; h(jxj)), i.e., h(n) has to decide correctly
only A =n (instead of A -n ).
A sequence of circuits Cn , n - 0, is called a circuit family for A, if for every n - 0,
Cn has n input gates, and for all n-bit strings x 1
It is well-known (see, e.g., [9]) that I univ can be chosen in such a way that advice
length and circuit size (i.e., number of gates) are polynomially related to each other.
More precisely, we can assume that there is a polynomial p such that the following
holds for every set A.
ffl If h is an advice function for A w.r.t. I univ , then there exists a circuit family
Cn , n - 0, for A of size jCn j - p(n
ffl If Cn , n - 0, is a circuit family for A, then there exists an advice function h
for A w.r.t. I univ of length jh(n)j - p(jC n j).
Moreover, we can assume that for every polynomial-time interpreter set I there is a
constant c I such that if h is an advice function for A w.r.t. I, then there exists an
advice function h 0 for A w.r.t. I univ of length jh 0 (n)j I for all n.
The following lemma is obtained by a direct diagonalization (cf. the corresponding
result in [21]). A set S is called -printable (see [16]) if there is a polynomial-time
oracle transducer T and an oracle set A 2 C such that on any input 0 n , T A outputs
a list of all strings in S -n .
Lemma 5.2. For every fixed polynomial s, there is a \Delta P
3 -printable set A such that
every advice function h for A is of length jh(n)j - s(n), for almost all n.
Proof. For a given n, be the sequence of strings of length n,
enumerated in lexicographic order. Consider the two sets Have-Advice and Find -A
defined as follows:
Have-Advice ,
9 a j+1 \Delta \Delta \Delta a
Since there are only 2 strings w in \Sigma !s(n) , at least one pair of the
form hn; a 1 \Delta \Delta \Delta a s(n) i is not contained in Have-Advice (provided that s(n) - 2 n ). Let
ff n denote the lexicographically smallest such pair hn; a 1 \Delta \Delta \Delta a s(n) i, i.e., there is no
advice of length smaller than s(n) that accepts the strings x according to
A as the set of all strings x i (jx n) such that 1 - i - s(n) - 2 n and the
ith bit of ff n (i.e., a i ) is 1. By a binary search using oracle Find -A, ff n is computable
in polynomial time. Since Have-Advice is in NP and thus Find -A is in NP(NP), it
follows that A is P(NP(NP))-printable. Since furthermore, for almost all n, A =n has
no advice of length smaller than s(n), the lemma follows.
Corollary 5.3. For every fixed polynomial s, there is a set A in ZPP(NP) that
does not have circuits of size s(n).
Proof. If NP does not have polynomial-size circuits, then we can take
Otherwise, by Corollary 4.1, and thus the theorem easily follows from
Lemma 5.2.
Corollary 5.4. Let f be an increasing, time-constructible, super-polynomial
function. Then ZPTIME[f(n)](NP) contains a set A that does not have polynomial-size
circuits.
14 J. K -
OBLER AND O. WATANABE
Proof. If NP does not have polynomial-size circuits, then we can take
Otherwise, by Corollary 4.1, and thus it follows from Lemma 5.2
that there is a set B in ZPTIME[n k ](NP) such that every advice function h for B
is of length jh(n)j - n for almost all n. By the proof technique of Lemma 5.2, we
can assume that in all length n strings of B, 1's only occur at the O(log n) rightmost
positions. Now consider the following set (where n denotes jxj)
and the interpreter set
Clearly, A belongs to ZPTIME[f(n)](NP) and I belongs to P. Furthermore, if h is
an advice function for A, then we have for every y of the form 0 bf(n) 1=k c\Gamman x,
that
where h 0 (n) is a suitable advice function of length jh 0 (n)j I . Thus, it
follows for almost all n that
This shows that the length of h is super-polynomial.
Corollary 5.5. In every relativized world, ZPEXP(NP) contains sets that do
not have polynomial-size circuits.
We remark that the above results are proved by relativizable arguments. On the
other hand, Harry Buhrman [12] and independently Thomas Thierauf [36] pointed out
to us that Theorem 4.8 (which is proved by a non-relativizable proof technique) can be
used to show that MA exp " co-MA exp contains non P/poly sets. Here, MA exp denotes
the exponential-time version of Babai's class MA [5]. That is, MA
where a language L is in MA[f(n)], if there exists a set B 2 DTIME[O(n)] such that
for all x of length n,
where z is chosen uniformly at random from \Sigma f(n) .
Corollary 5.6. [12, 36] MA exp " co-MA exp contains sets that do not have
polynomial size circuits.
Since there exist recursive oracles relative to which all sets in EXP(NP) have polynomial
size circuits [39, 17], it is not possible to extend Corollary 5.5 by relativizing
techniques to the class EXP(NP).
6. Concluding remarks. An interesting question concerning complexity classes
C that are known to be not contained in P/poly but are not known to have complete
sets is whether the existence of sets in C \Gamma P/poly can be constructively shown. For
example, by Corollary 5.5 we know that the class ZPEXP(NP) contains sets that
do not have polynomial-size circuits. But we were not able to give a constructive
proof of this fact. To the best of our knowledge, no explicit set is known even in

Acknowledgments

For helpful discussions and suggestions regarding this work we are very grateful to
H. Buhrman, R. Gavald'a, L. Hemaspaandra, M. Ogihara, U. Sch-oning, R. Schuler,
and T. Thierauf. We like to thank H. Buhrman, L. Hemaspaandra, and M. Ogihara
for permitting us to include their observations in the paper.



--R

On hiding information from an oracle
Queries and concept learning
Arithmetization: A new method in structural complexity

a randomized proof system and a hierarchy of complexity classes



Structural Complexity Theory I
Introduction to the Theory of Complexity
Oracles and queries that are sufficient for exact learning

Universal classes of hash functions
Bounding the complexity of advice functions
Computational complexity of probabilistic complexity classes
Computation times of NP sets of different densities
On relativized exponential and probabilistic complexity classes
How hard are sparse sets?
Random generation of combinatorial structures from a uniform distribution


Some connections between nonuniform and uniform complexity classes
Journal of Computer and System Sciences


Strong nondeterministic polynomial-time reducibilities

Algebraic methods for interactive proof systems
On sparse hard sets for counting classes
On polynomial-time bounded truth-table reducibility of NP sets to sparse sets
Computational Complexity
On simultaneous resource bounds

A complexity theoretic approach to randomness
Probabilistic polynomials

Counting classes are at least as hard as the polynomial-time hierarchy
Complexity classes defined by counting quantifiers
Relativized circuit complexity
Some consequences of non-uniform conditions on uniform classes
Robustness of probabilistic computational complexity classes under definitional perturbations
--TR

--CTR
Christian Glaer , Lane A. Hemaspaandra, A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions, ACM SIGACT News, v.31 n.4, p.39-51, Dec. 2000
Valentine Kabanets , Jin-Yi Cai, Circuit minimization problem, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.73-79, May 21-23, 2000, Portland, Oregon, United States
Lane A. Hemaspaandra , Mitsunori Ogihara , Gerd Wechsung, Reducing the number of solutions of NP functions, Journal of Computer and System Sciences, v.64 n.2, p.311-328, March 2002
Rahul Santhanam, Circuit lower bounds for Merlin-Arthur classes, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Lane A. Hemaspaandra, SIGACT News complexity theory column 32, ACM SIGACT News, v.32 n.2, June 2001
Jin-Yi Cai , Venkatesan T. Chakaravarthy , Lane A. Hemaspaandra , Mitsunori Ogihara, Competing provers yield improved Karp-Lipton collapse results, Information and Computation, v.198 n.1, p.1-23, April 10, 2005
Piotr Faliszewski , Lane Hemaspaandra, Open questions in the theory of semifeasible computation, ACM SIGACT News, v.37 n.1, March 2006
Lance Fortnow, Beyond NP: the work and legacy of Larry Stockmeyer, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Johannes Kbler , Rainer Schuler, Average-case intractability vs. worst-case intractability, Information and Computation, v.190 n.1, p.1-17, April 10, 2004
polynomial-size circuits;lowness;advice classes;randomized computation