
% Universitat Politecnica de Catalunya
% Dept. of LSI
% Technical Report LSI-91-17
% September 15, 1991

\documentstyle[11pt, titlepage]{article}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{dfntn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\rm}{\end{dfntn}}
\newenvironment{proof}
    {\pagebreak[1]{\narrower\noindent {\bf 
Proof:\quad\nopagebreak}}}{\QED}
\newcommand{\yyskip}{\penalty-50\vskip 5pt plus 3pt minus 2pt}
\newcommand{\blackslug}{\hbox{\hskip 1pt
        \vrule width 4pt height 8pt depth 1.5pt\hskip 1pt}}
\newcommand{\QED}{{\penalty10000\parindent 0pt\penalty10000
        \hskip 8 pt\nolinebreak\blackslug\hfill\lower 8.5pt\null}
        \par\yyskip\pagebreak[1]}
 
\newcommand{\PH}{{\rm PH}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\coNP}{\mbox{\rm co-{\rm NP}}}
\newcommand{\FP}{{\rm FP}}
\let\paragraph\P
\renewcommand{\P}{{\rm P}}
\newcommand{\PARITY}{\oplus}
\newcommand{\OR}{\vee}
\newcommand{\AND}{\wedge}
\newcommand{\implies}{\mathrel{\Rightarrow}}
\newcommand{\Iff}{\mathrel{\Leftrightarrow}}
\newcommand{\PARITYP}{\PARITY\space\space\P}
\newcommand{\PP}{{\rm PP}}
\newcommand{\BPP}{{\rm BPP}}
\newcommand{\EP}{{\rm C}_=\P}
\newcommand{\coEP}{{\rm C}_{\not =}\P}
\newcommand{\T}{{\rm T}}
\newcommand{\ESAT}{{\rm ESAT}}
\newcommand{\ESATbar}{{\overline {\rm ESAT}}}
\newcommand{\ebarande}{\ESATbar~\AND~\ESAT}
\newcommand{\eorebar}{\ESAT~\OR~\ESATbar}
\newcommand{\BH}{{\rm BH}}
\newcommand{\coBH}{\mbox {\rm co-}\BH}
\newcommand{\mod}{{\rm mod}}
\newcommand{\Tmaj}{T_{3/4}}
\newcommand{\nat}{{\rm I\kern -.16em N}}

\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{\oddsidemargin}
\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\topmargin}{-0.0in}
 
\sloppy

\begin{document}
\title{On the Power of Deterministic Reductions to $\EP$}

\author{          Frederic Green
               \thanks {Research supported by
                  a grant from the Direcci{\'o}n General de Investigaci{\'o}n
                         Cient{\'\i}fica y T{\'e}cnica (DGICYT),
                         Spanish Ministry of Education, while the author
                         was visiting the Facultat d'Inform{\`a}tica,
                         Universitat Polit{\`e}cnica de
                         Catalunya, Barcelona.}
                \\{\small Department of Mathematics and Computer Science}
                \\{\small Clark University}
                \\{\small Worcester, Massachusetts 01610}
                \\{\small fgreen@clarku.bitnet}
                \\{\small September 15, 1991}}
\date{}
\maketitle
 
\begin{abstract}
  The counting class $\EP$, which captures the notion of ``exact counting",
while extremely powerful under various nondeterministic reductions, is
quite weak under polynomial-time deterministic reductions. We discuss
the analogies between {\rm NP} and co-$\EP$, which allow us to derive 
many
interesting results for such deterministic reductions to co-$\EP$.
We exploit these results to obtain some
interesting oracle separations. Most importantly, we show that there 
exists
an oracle $A$ such that $\PARITYP^A \not \subseteq \P^{\EP^A}$ and
$\BPP^A \not \subseteq \P^{\EP^A}$. Therefore,
techniques that would prove that $\EP$ and $\PP$ are
polynomial-time Turing equivalent, or that $\EP$ is polynomial-time
Turing hard for the polynomial-time hierarchy, would not relativize.
\end{abstract}
 
\section{Introduction}
  The class $\EP$ (see section 2 for precise definitions) is an
extremely powerful counting class which captures the notion of ``exact
counting". It can be characterized by nondeterministic machines which 
accept
if and only if the number of accepting paths is exactly equal to a given
number. The power of $\EP$ can be seen from the following facts:\\

\noindent{\bf Facts:}

 (i) $\PP^{\PH} \subseteq \NP^{\EP}$.

 (ii) $\EP^{\PH} \subseteq {\rm BP} \cdot \EP$.\\

Fact (i) is a consequence of Toda's theorem \cite{Toda} that
$\PP^{\PH} \subseteq \P^{\PP}$ combined with a theorem of Tor{\'a}n
\cite{Toran}
which states $\NP^{\PP} = \NP^{\EP}$. It is significant since it states
that $\EP$ is hard for the polynomial hierarchy under nondeterministic
reductions. Fact (ii) was proved by Toda and Ogiwara \cite{TO}, and in
a stronger form by Tarui \cite{Tarui}. It is significant since
it says that $\EP$ is hard for the polynomial hierarchy under randomized
reductions. 

  The purpose of this paper is to observe that although $\EP$ is quite
powerful under nondeterministic or randomized reductions, nevertheless
under deterministic reductions it appears to be quite weak. 
Specifically, we address primarily the following questions:\\

(1) How powerful are polynomial-time Turing reductions to $\EP$?

(2) How powerful is a constant number of queries to $\EP$?\\

In attempting to answer these questions, we find that in
many respects the classes $\NP$ and 
{\em co-}$\EP$ (or alternatively $\coEP$) are similar. In particular,
 NP has a complete problem,
and is closed under union, intersection, polynomial-time disjunctive
and conjunctive reductions, and polynomial-time nondeterministic many-one
reductions. The class $\coEP$ has all of these properties.
It turns out that many proofs about restricted Turing
reductions to NP, the Boolean hierarchy over NP, and related notions,
 depend only on these
properties. Thus many interesting results about NP can be easily 
translated into
analogous results about $\coEP$. For example, we find that the
closure of $\EP$ under polynomial time truth-table reductions is exactly
as powerful as the closure under polynomial-time Turing reductions with
logarithmically many queries (i.e., $\P^{\EP}_{tt} = \P^{\EP}_{O(log(n))-
\T}$;
see theorem ~\ref{le:tt-reductions} and the remarks preceeding it).
However, our main interest is in exploiting these results in order to
answer the above questions.

   Some insight into question 2 is gained immediately by
examining the analogies between NP and $\EP$. 
Using these analogies we find here that the query and Boolean
hierarchies are just as
closely intertwined for $\EP$ as they are for NP \cite{Bei}.
We also find that
the proof of Kadin \cite{K} and Chang and Kadin \cite{KC} which shows that 
if
 the Boolean hierarchy over
NP collapses then the polynomial hierarchy collapses, also works for the
Boolean hierarchy over $\EP$. Thus if the Boolean hierarchy over $\EP$
collapses to some finite level, we find that the polynomial hierarchy
{\sl relative to PP} collapses to the $\Delta_2$ level {\sl relative to PP}.
This links a collapse of the query hierarchy over $\EP$ to a collapse of
the polynomial hierarchy relative to PP.
Beigel, Chang and Ogiwara \cite{BCO}
have independently proved a stronger version
of this theorem, using techniques somewhat different than those of Chang and
Kadin.
Note that this is in sharp contrast to the query hierarchy over PP, which
collapses to PP \cite{BRS}. These results are discussed in section 3.

 Nothing is
 known about question 1, not even oracle separations, and up until now
there has been
no reason (other than intuition) to believe that $\P^{\EP}$ is any less
powerful than $\P^{\PP}$. The intuition is quite strong, however. With
queries to $\PP$, there is a well-known binary search algorithm which
enables us to count the number of accepting paths in nondeterministic
computations. A $\PP$ oracle provides us pairs of the form
$\langle x, y \rangle$ such that $f(x) \ge y$ and $f \in \#\P$, from which
it is possible to determine
the value of $f(x)$ by binary search on $y$. 
On the other hand, a $\EP$ oracle only
provides information about the graph of a $\#\P$ function, that is,
pairs of the form $\langle x, y \rangle$ such that $f(x)=y$. It seems
obvious that it would be impossible to determine the value of $f$ from
this information (in polynomial time) in the absence of nondeterminism.
Thus for example, although it is well known that $\PARITYP \subseteq 
\P^{\PP}$,
it is not at all clear that $\PARITYP \subseteq \P^{\EP}$. Indeed, it does
 not seem
likely that any of the classes $\PARITYP$, PP, or PH are in $\P^{\EP}$.

  In this paper, we obtain oracle separations of $\P^{\EP}$ and
$\P^{\PP}$. Specifically, we
construct an oracle $A$ relative to which $\PARITYP$ and BPP are not 
contained
in $\P^{\EP}$ (see section 5).
A direct consequence of the separation of BPP from $\P^{\EP}$
are separations of both PP and $\Sigma_2^p \cap \Pi_2^p$ from $\P^{\EP}$.
The constructions are based on circuit lower bounds, building on a result
of Gundermann, Nasser and Wechsung \cite{GNW},
 as well as a new characterization of
$\P^{\EP}$ (easily proved using the analogies between $\coEP$ and NP). The
circuit lower bounds are for depth-2 circuits consisting of a single
``equals" gate over AND-gates (called ``EQ circuits"), and are actually
lower bounds on the fanin of the AND-gates rather than lower bounds
on the size of the circuits.

   We finally turn to oracle results relating to question 2. 
Gundermann, Nasser and Wechsung
\cite{GNW} obtained an
oracle separation of the Boolean hierarchy over $\EP$. Since the Boolean
hierarchy is intertwined with the query hierarchy,
in some relativized world, $k+1$
queries to $\EP$ are more powerful than $k$.
Here we consider the question of whether $k+1$ questions to {\sl NP}
cannot be answered by $k$ questions to $\EP$.
In fact we find that in some
relativized world, there are sets that are recognizable with $k+1$ queries 
to NP
that cannot be recognized with $k$ queries to $\EP$. One may regard this
as a generalization of the result of Tor{\'a}n \cite{ToranThesis} that relative
to some oracle, NP is not contained in $\EP$. In order to do this
we again adapt the technique of \cite{GNW} (section 4)
to appropriate circuit problems.
In section 6 an oracle is constructed which separates
every level of the Boolean hierarchy over NP from a level of the Boolean
hierarchy over $\EP$. Clearly this simultaneously  separates the query
hierarchies over $\NP$ and $\EP$. The resulting construction for the
Boolean hierarchy over NP is simpler than existing
ones \cite{Caietal}
although it apparently is not powerful enough to obtain random oracle 
results
(see \cite{Cai}).


\section{Preliminaries}

   We assume the reader is familiar with complexity classes such as
P, NP, $\Sigma_k^p$ and PH (see, e.g., \cite{BDG}).
 Let $N$ be a polynomial time-bounded
nondeterministic Turing machine.
Then $\#acc_N(x)$ denotes the number of accepting paths of $N$ on input 
$x$.
$\#\P$ is the class of functions $f$ such that there exists a polynomial
time-bounded nondeterministic machine $N$ such that for all $x$,
$f(x) = \#acc_N(x)$.

  The class $\EP$ \cite{Wagner} 
is defined to be the set of languages $L$ such that
there exist functions $f \in \#\P$, $t \in \FP$ and
for all $x$, $x \in L$ if and only if $f(x)=t(x)$.
The notation ${\mbox {\rm co-}\EP}$ denotes the class of sets whose
 complements are
in $\EP$. We will denote ${\mbox {\rm co-}\EP}$ alternatively by $\coEP$.
PP is similarly defined, but with ``$f(x)=t(x)$" replaced by
``$f(x) \ge t(x)$".

  It was recently remarked in \cite{GNW} that in the definitions above one
can replace the function $t \in \FP$ by a function $g \in \#\P$, and
still obtain the same classes.
We can furthermore assume without loss of generality that, in the 
resulting
alternative definition of $\EP$, $f(x) \ge g(x)$ for all $x$.

   $\PARITYP$ is defined as the set of languages $L$ such that there exists
a function $f \in \#\P$ and for all $x$, $x \in L$ if and only if
$f(x)$ is odd.

   We denote by ESAT the standard complete language \cite{Wagner} for 
$\EP$:
$\ESAT = \{\langle {\cal F}, n \rangle | {\cal F} $ is a Boolean formula
with exactly $n$ satisfying truth assignments $\}$. Obviously $\ESATbar$
is complete for $\coEP$.

  We now present other definitions that will be important in later 
sections.
  Let $A$ and $B$ be sets. We say $A \le_m^{\NP} B$ if and only if there
exist a polynomial $p$ and a function $f \in \FP$ such that for any $x$,
$x \in A$ if and only
if $(\exists z, 1 \le |z| \le p(|x|))(f(\langle x,z \rangle) \in B)$.
For any complexity class ${\cal C}$, the notation $\exists {\cal C}$
denotes the class of all sets $L$ such that there exists a polynomial
$p$ and a set $B \in {\cal C}$ such that for all $x$,
$x \in L \Iff (\exists z, |z| \le p(|x|))(\langle x,z\rangle \in B)$.
A set $A$ is {\sl conjunctive truth-table reducible} to a set $B$,
(symbolically $A \le^p_{c-tt} B$) if there exists a function
$f \in FP$ such that for any $x$, $f(x) = \langle q_1,...q_k \rangle$,
and $x \in A$ iff $(\forall i, 1 \le i \le k)(q_i \in B)$.
For any complexity class ${\cal C}$, $\P_{k-\T}^{\cal C}$ denotes the
class of sets polynomial time Turing reducible to ${\cal C}$ with no more
 than $k$ queries,
$\P_{tt}^{\cal C}$ the class of sets polynomial-time truth-table reducible
to ${\cal C}$, and $\P_{O(f(n))-\T}^{\cal C}$ the class of sets
Turing reducible to ${\cal C}$ with $O(f(n))$ queries.
   The {\sl query hierarchy} over ${\cal C}$
is defined as $\bigcup_{k=1}^{\infty} \P^{\cal C}_{k-\T}$.

  Let ${\cal C}$ be a complexity class. Following \cite{Caietal},
we define the {\sl Boolean hierarchy
over ${\cal C}$} inductively as follows: Let $\BH_1({\cal C}) = {\cal C}$,
and, for all $k > 1$,
$$       \BH_{2k}({\cal C}) =
         \{L | L = L_1 \cap {\overline L_2}, L_1 \in \BH_{2k-1}({\cal C}),
                                            L_2 \in {\cal C}\},$$
$$       \BH_{2k+1}({\cal C}) =
         \{L | L = L_1 \cup L_2, L_1 \in \BH_{2k}({\cal C}),
                                            L_2 \in {\cal C}\}.$$
Finally, $\BH({\cal C}) = \bigcup_{k=1}^{\infty}(\BH_k({\cal C}))$.
Boolean hierarchies over general complexity classes have been
studied previously in \cite{BB}.

 The Boolean hierarchy can be defined in many different ways. We will
make use of the following two characterizations which hold for 
complexity
classes ${\cal C}$ that are closed under union, which will be the
case for the classes we consider in this paper. The first is a
convenient normal form, and the second shows that for such classes
the Boolean hierarchy is the same as the difference hierarchy
\cite{Caietal}.

\begin{proposition}\label{le:normal-form-1}
 Suppose ${\cal C}$ is closed under union. For any $k > 1$,
$$\BH_{2k}({\cal C}) = {\bigcup \limits_{i=1}^k {L_i}}$$
where for each $i$, $L_i = L_{i1} \cap {\overline L}_{i2}$, $L_{i1}, L_{i2}
\in {\cal C}$, and
$$\BH_{2k+1}({\cal C}) = ({\bigcup \limits_{i=1}^k {L_i}}) \cup L_{k+1}$$
where the $L_i$, $1 \le i \le k$, are as above, and $L_{k+1} \in {\cal C}$.
\end{proposition}

\begin{proposition}\label{le:normal-form-2}
Suppose ${\cal C}$ is closed under union. Then
for all $k > 1$,
$$       \BH_{k}({\cal C}) =
         \{L | L = L_1 \cap L_2, {\overline L}_1 \in \BH_{k-1}({\cal C}),
                                         L_2 \in {\cal C}\}.$$
\end{proposition}
%\begin{proof}
%  The proof is by induction. The base case is obvious from the definition
%of $\BH_2({\cal C})$.
%
%   Assume by hypothesis that for some $k > 2$ 
%$$       \BH_{2k}({\cal C}) =
%         \{L | L = L_1 \cap L_2, {\overline L}_1 \in \BH_{2k-1}({\cal C}),
%                                         L_2 \in {\cal C}\}.$$
%By definition, for any $L \in \BH_{2k+1}({\cal C})$, we can write
%$L = L_1 \cup L_2$, $L_1 \in \BH_{2k}({\cal C}), L_2 \in {\cal C}$.
%Using the inductive hypothesis, we can write $L_1 = L_3 \cap L_4$, 
where
%${\overline L}_3 \in \BH_{2k-1}({\cal C}), L_4 \in {\cal C}$. Thus
%$L= (L_3 \cap L_4) \cup L_2 = (L_3 \cup L_2)\cap(L_4 \cup L_2)$ where
%we have used the distributive law. Now $L_4 \cup L_2 = L'_4$, where
%$L'_4 \in {\cal C}$ since ${\cal C}$ is closed under union. Also
%$L_3 \cup L_2 = L'_3$ where $L'_3 \in \coBH_{2k}({\cal C})$ by
%definition. Thus for any $L \in \BH_{2k+1}({\cal C})$ we can write
%$L = L'_3 \cap L'_4$, where ${\overline L'}_3
%\in \BH_{2k}({\cal C})$ and $L'_4 \in {\cal C}$, which proves the
%inductive step for $2k$.
%
%   The proof for $2k+1$ is similar.
%\end{proof}

\section{Analogies Between NP and C$_{\not =}$P}

  It has been known for some time that $\EP$ is closed under intersection
(\cite {Toran}, \cite{Wagner}). In \cite{Toran} it was also proved
that $\EP$ is closed under unbounded cartesian product which implies
that it is closed under (polynomial-time) 
conjunctive truth-table reductions. The
proof of this fact is similar to the proof that $\EP$ is closed under
intersection. The closure of $\EP$ under union was proved in
\cite{GNW}. Again, using essentially the same proof as for the
closure under union it is easy to see that $\EP$ is closed
under polynomial-time disjunctive truth-table reductions.
Translating these
results into the context of $\coEP$, we find that $\coEP$ is closed
under union, intersection, and both disjunctive and conjunctive
polynomial-time truth-table reductions.
That $\coEP$ is closed under $\le^{\NP}_m$-reductions
is a simple observation, and is well-known.
For completeness, we give a proof here.

\begin{proposition}\label{le:closure}
$\coEP$ is closed under $\le_m^{\NP}$-reductions.
\end{proposition}
\begin{proof}
  Let $L \in \coEP$ and suppose $L' \le_m^{\NP} L$. We will show that
$L' \in \coEP$. We know that there exist functions $f,g \in \#\P$
that for any $w$, $f(w) \ge g(w)$ and $w \in L$ if and only if
$f(w) \not = g(w)$.
Since $L' \le_m^{\NP} L$, there exists a polynomial $p$ and a function
$h \in \FP$ such that
   $x \in L' \Iff (\exists z, |z| \le p(|x|))
                     (f(h(\langle x,z \rangle))
                                    \not = g(h(\langle x,z \rangle))$.
Since for any $w$, $f(w) \ge g(w)$, the predicate
$(\exists z, |z| \le p(|x|))(f(h(\langle x,z \rangle))
                                     \not = g(h(\langle x,z \rangle))$
is true if and only if
$\sum \limits_z {f(h(\langle x,z \rangle))} \not =
 \sum \limits_z {g(h(\langle x,z \rangle))}$. But then using standard
techniques we can implement these sums in terms of $\#\P$ machines, 
i.e.,
there exist nondeterministic, polynomial time bounded machines $N'_1$ 
and
$N'_2$ such that for all $x$,
          $x \in L' \Iff \#acc_{N'_1}(x) \not = \#acc_{N'_2}(x)$.
Hence $L' \in \coEP$.
\end{proof}

   For the most part, we make use of this fact in the following
form, which says that $\coEP$ is closed under existential quantification.

\begin{corollary}\label{le:exists-c}
$\exists \coEP = \coEP$.
\end{corollary}

Now many interesting results can be
derived using analogous proofs for NP, with $\coEP$ playing the role of
NP. 
%In some cases we will omit the proofs, but to illustrate the
%correspondence we will include the more compact ones.
For the first result, recall that
truth-table reductions to NP are exactly as powerful as Turing reductions
with logarithmically many queries, i.e., 
$\P^{\NP}_{O(log(n))-\T} = \P^{\NP}_{tt}$ (\cite{BussHay},
\cite{Hem}).
 Here we find the same is true of
$\EP$. This result has also been found by Toda \cite{TodasTalk}.
 The result and the
proof reported here were obtained independently
\footnote{Subsequently Ogiwara \cite{Ogiwara}
has substantially generalized
this result, exhibiting sufficient conditions for any complexity class
${\cal C}$ to obey $\P^{\cal C}_{tt} = \P^{\cal C}_{O(log(n))-\T}$. He
has also proved the very nice result that $\EP$ is closed under
positive Turing reductions (and exhibits sufficient conditions
for any class to have this property).}. The proof we give is typical
of those that use the closure properties shared by NP and $\coEP$.

\begin{theorem}\label{le:tt-reductions}
$\P^{\EP}_{O(log(n))-\T} = \P^{\EP}_{tt}$.
\end{theorem}
\begin{proof}
   The inclusion from left to right is straightforward: the
query tree of a $\P^{\EP}_{O(log(n))-\T}$ machine can be written down in
polynomial time, and a polynomial size truth table can be
constructed from the query tree.

   The inclusion from right to left follows from an argument similar to the
one used to prove $\P^{\NP}_{tt} \subseteq \P^{\NP}_{O(log(n))-\T} $, aided 
by
corollary ~\ref{le:exists-c}.
 Let $M^A$ be a $\P^{\EP}_{tt}$ machine, where (without loss of
generality) $A \in \coEP$ (e.g., $A = \ESATbar$), and $M^A$ is
bounded by the polynomial $p$. On input $x$, $|x|=n$, suppose $M$ produces 
the
queries $S=\{q_1, q_2, ... q_{p(n)}\}$. We will show how to simulate the
rest of the computation of $M^A$ using logarithmically many queries to
$\coEP$. First, we show that with logarithmically many queries to 
$\coEP$,
we can determine the number $l$ of $q_i$'s such that $q_i \in \ESATbar$.
Consider a nondeterministic machine $N$ that, on input
$\langle S,k \rangle$, guesses
$k$ elements of $S$ and then accepts iff all the guessed strings are
elements of $\ESATbar$. Using the closure of $\coEP$ under
polynomial-time conjunctive reductions,
it is easy to see that $N$ is an $\exists \coEP$ machine.
By corollary ~\ref{le:exists-c}
we can simulate $N$ by some $\coEP$ machine $N'$. Note that
by binary search on $k$, since $0 \le k \le p(n)$, we can determine $l$
with log many queries. We now know both $l$, the number of positive 
answers
to the queries in $S$, as well as $p(n)-l$, the number of negative answers.
With one extra query to $\coEP$ we can simulate $M^A$. We construct a
nondeterministic machine $N''$ which guesses $l$ elements of $S$, and
rejects if any one of them is in $\ESAT$. If all the guessed elements
are in $\ESATbar$, then we know the set of queries with positive
answers
and with negative answers. Using this information, simulate $M^A$ 
directly,
accepting if and only if $M^A$ accepts. It is easy to see that $N''$ is
an $\exists \coEP$ machine, and therefore, again using corollary
~\ref{le:exists-c}, a
$\coEP$ machine. Hence with $O(log(n))$ queries to $\coEP$ we can 
simulate
$M^A$.
\end{proof}

  It is well known that $\NP= \coNP$ if and only if $\PH = \NP$. A
similar phenomenon occurs if $\EP$ is closed under complement.

\begin{corollary}\label{le:ep-eq-coep}
$\EP = \coEP$ if and only if $\PH^{\PP} = \EP$.
\end{corollary}
\begin{proof}
   The ``if" part is clear.
Then suppose $\EP = \coEP$. Tor{\'a}n \cite{Toran} has proved that 
$\NP^{\PP} = \NP^{\EP} = \exists \EP$. Hence if $\EP = 
\coEP$,
$\NP^{\PP} = \exists \EP = \exists \coEP = \coEP = \EP$.
\end{proof}

   We conclude this section with some remarks on the Boolean and query
hierarchies. Not surprisingly, many of the properties of $\BH(\NP)$ are
shared by $\BH(\EP)$. For example, the levels of $\BH(\EP)$ have complete
problems analogous to those for the levels of $\BH(\NP)$.
Another important example for this paper is that,
just as in the case of NP, there
is a tight intertwining relationship between the Boolean and query 
hierarchies
over $\EP$. The proof of this fact follows Beigel's proof for NP \cite{Bei}.
In fact it was pointed out in \cite{Bei} that the proof
for this theorem only depends on the existence of
a complete problem, and closure under intersection, union and
$\le_m^{\NP}$-reducibility.

\begin{theorem}\label{le:intertwining}
For all $k \ge 1$,
 $\BH_{2^k-1}(\EP) \cup \coBH_{2^k-1}(\EP)
     \subseteq \P^{\EP}_{k-\T} 
     \subseteq \BH_{2^k}(\EP) \cap \coBH_{2^k}(\EP)$.
\end{theorem}

   It is natural to ask if the Boolean hierarchy over $\EP$ collapses, or,
equivalently, if the query hierarchy over $\EP$ collapses to some finite
level. (Corollary ~\ref{le:ep-eq-coep} represents a first step in this
direction.) As mentioned in the introduction,
up to now the only known separation is a relativized one (see \cite{GNW} 
and
section 6). In contrast for NP, structural relationships between
the Boolean hierarchy over NP and the polynomial hierarchy are known.
It was proved by Kadin that if the Boolean hierarchy
collapses to a finite level then PH collapses to $\P^{\NP^{\NP}}$
\cite{K},\cite{KC}. Stated more precisely,
if for any $k$, $\BH_{k}(\NP) = \coBH_k(\NP)$ then $\PH
\subseteq \Delta_2^{\NP}$ (in fact, Chang and Kadin show the
much sharper consequence $\PH \subseteq \BH_k(\NP^{\NP})$).
Another way of saying this is that if for any $k$,
$\BH_{k}(\NP) = \coBH_k(\NP)$, then $\PH^{\NP}
\subseteq \BH_k(\NP^{\NP})$.
We observe here that Chang and Kadin's proof of this fact
carries over directly if we put $\coEP$ in place of NP. 
Thus if we
replace the NP's in the hypothesis $\BH_{k}(\NP) = \coBH_k(\NP)$
with $\EP$'s, we can replace the oracle NP's in the conclusion
with $\EP$, that is the conclusion becomes
$\PH^{\EP} \subseteq \BH_k(\NP^{\EP})$. Since $\NP^{\PP} = \NP^{\EP}$
and $\PH^{\PP} = \PH^{\EP}$ \cite{Toran}, we find the following

\begin{theorem}\label{le:collapse-1}
If for any $k$, $\BH_{k}(\EP) \subseteq \coBH_k(\EP)$ then $\PH^{\PP}
\subseteq \BH_k(\NP^{\PP}) \subseteq \P^{\NP^{\PP}}_{k-\T}$.
\end{theorem}

Independently, Beigel, Chang and Ogiwara \cite{BCO}
have made the same observation,
but they present their own simpler proof of this, using a ``mind change"
technique that allows them to derive a stronger result.

  Thus making use of theorem ~\ref{le:intertwining} we have,

\begin{corollary}\label{le:collapse-2}
If for any $k$, $\P^{\EP}_{(k+1)-\T} \subseteq \P^{\EP}_{k-\T}$, then
$\PH^{\PP} \subseteq \P^{\NP^{\PP}}$.
\end{corollary}

 The proof of theorem ~\ref{le:collapse-1} exploits the analogy between
$\coEP$ and NP. Using the terminology of \cite{K},
Corollary ~\ref{le:exists-c}
 allows us to do ``oracle replacement" in nondeterministic computations
when it is possible to find ``small $\coEP$ machines" for $\EP$. The 
``hard string/easy string" argument similarly holds with $\ESATbar$
playing the role of SAT. The reason their proof works is that the
only essential properties of NP that are used are the existence of
a complete problem, and closure under
$\le^{\NP}_m$-reductions and conjunctive reductions, all
of which are also properties of $\coEP$.

   Rather than reproduce the full proof of Chang and Kadin,
we will indicate how it works by briefly sketching the proof for the
following special case, analogous to the example proved in
their paper: If $\BH_2(\EP) \subseteq \coBH_2(\EP)$
then $\PH^{\PP} \subseteq \P^{\NP^{\PP}}_{2-\T}$. First note that
the following sets are $\le^p_m$-complete
for $\BH_2(\EP)$ and $\coBH_2(\EP)$, respectively:
$$\ebarande = 
  \{\langle x_1,x_2 \rangle | x_1 \in \ESATbar~{\rm and}~x_2 \in \ESAT\}$$
$$\eorebar = 
  \{\langle x_1,x_2 \rangle | x_1 \in \ESAT~{\rm or}~x_2 \in \ESATbar\}.$$
Now assume $\BH_2(\EP) \subseteq \coBH_2(\EP)$. Then
$\ebarande \le^p_m \eorebar$, where the reduction is via some polynomial
time computable function $h$. A string $x$ is called {\sl hard} if
$x \in \ESAT$ and for any $y$ where $|y| \le |x|$,
$\pi_2(h(y,x)) \in \ESAT$. Otherwise $x$ is said to be easy. If a
string $x$ is known to be easy, we can determine that $x \in \ESAT$
using a $\coEP$ algorithm: guess a $y$ with $|y| \le |x|$, and accept if
$\pi_2(h(y,x)) \in \ESATbar$ (actually the algorithm is $\exists \coEP$,
but this is the same as $\coEP$). On the other hand, if there exists a
hard string $z$ of a given length $m$, the hard string can be used to
find a $\coEP$ algorithm for all of $\ESAT$ up to length $m$. That is,
given any string $x$, $|x| \le m$, compute $\pi_1(h(x,z))$
and verify that it is in $\ESATbar$. It is not hard to show that
$x \in \ESAT \Iff \pi_1(h(x,z)) \in \ESATbar$. Note that the problem
of determining if a string is hard is in $\forall \EP = \EP$, and
therefore the problem of determining if there exists a hard string
of a given length is in $\NP^{\EP}$. We can now argue that
$\NP^{\NP^{\EP}} \subseteq \P^{\NP^{\EP}}_{2-\T}$. Suppose
$L \in \NP^{\NP^{\EP}}$, in particular, $L=L(N)$,
where $N$ is an $\NP$-machine which makes queries to an $\NP^{\EP}$
oracle and whose run-time is bounded by $r$.
We will now describe a
$\P^{\NP^{\EP}}_{2-\T}$ algorithm for $L$.
Suppose we want to know if $x \in L$. Without loss of generality,
the queries that $N^{\NP}$ makes to $\EP$ have length exactly
equal to $p(r(|x|))$, for some polynomial $p$.
With one query to $\NP^{\EP}$ we can determine if there is
a hard string of length $p(r(|x|))$. With one last query to $\NP^{\EP}$
we can simulate $N$ using one
of the above algorithms to reduce ESAT to $\ESATbar$, depending on
whether or not there is a hard string of length $p(r(|x|))$,
as follows. If there is no hard
string of length $p(r(|x|))$, we know any query to $\EP$
 is easy and we can use the above ``easy string" guessing
algorithm (and the fact that $\NP^{\EP} = \exists \EP$)
to replace the $\NP^{\EP}$ oracle of
$N$ with a $\coEP$ oracle. If there is
a hard string of length $p(r(|x|))$, we can guess it, verify with
a query to $\EP$ that it is indeed hard, and then continue
the computation using the ``hard string" algorithm
to determine if $x \in L$. The latter is an $\NP^{\EP}$
computation. Both the easy and hard cases only require one extra
query to $\NP^{\EP}$. Thus $\NP^{\NP^{\EP}} \subseteq \P^{\NP^{\EP}}_{2-\T}$
and therefore $\PH^{\EP} \subseteq \P^{\NP^{\EP}}_{2-\T}$, which
implies $\PH^{\PP} \subseteq \P^{\NP^{\PP}}_{2-\T}$.

\section{EQ Circuits and Their Limitations}

   We define a family of circuits closely related to $\EP$.
An {\sl EQ circuit of size m, order s and threshold t} over the inputs
$X = \{x_1,...,x_n\}$
consists of a set of AND gates, $c_i, 1 \le i \le m$, where each AND gate
has fanin at most $s$ and the circuit outputs 1 if and only if
$\sigma(X)=t$, where by definition
$$\sigma (X) = \sum \limits_{i=1}^m c_i(X).$$
An {\sl NEQ circuit of size m, order s and threshold t} is defined similarly,
except that it outputs 1 if and only if $\sigma(X) \not = t$. (Note that
the AND-gates in these definitions can have negated variables. An AND
gate can have fanin 0 in which case by definition it outputs the constant 1.)

   We say that an EQ circuit $C$ on the inputs  $\{x_1,...,x_n\}$
is {\sl computable by a non-negative polynomial of degree $d$}
if there exists a
polynomial $p$ of degree $d$ with integer coefficients
in the variables $\{x_1,...,x_n\}$, and for all settings of the
$x_i$'s, the following conditions hold:
$p(x_1,...,x_n) \ge 0$,
and $C(x_1,...,x_n) = 1$ if and only if $p(x_1,...,x_n)=0$.
The notion that an NEQ circuit $C$
is computable by a non-negative polynomial is defined
precisely the same, except that $C(x_1,...,x_n) = 1$ if and only if
$p(x_1,...,x_n) \not =0$.

  Using a technique from \cite{GNW}, it is easy to
show that every EQ (resp. NEQ) circuit can be computed by a
non-negative polynomial.

\begin{proposition}\label{le:normalize}
  Let $C$ be an EQ circuit of size $m$ and order $s$.
Then $C$ is computable by a non-negative
polynomial $p$ with at most $(2^sm+1)^2)$ terms and degree at most $2s$.
\end{proposition}
\begin{proof}
We have that $C=1$ if and only if
$$\sum \limits_{i=1}^m c_i(X) = t$$
where $X = \{x_1,...,x_n\}$. Then $C=1$ if and only if
$$(\sum \limits_{i=1}^m c_i(X) - t)^2 = 0.$$
Note that the left hand side is always $\ge 0$.
Rewrite each negated variable ${\overline x}_i$ as $1-x_i$. Expressing
each AND-gate $c_i$ as a product, expand to obtain a sum of terms
of the form $\prod_{i \in S} x_i$ (note that $||S|| \le s$), or
the constant
term 1. Note that the coefficients of the non-constant terms
can be arbitrary, possibly negative integers (not just 0 or 1).
This yields at most $2^s$ terms for each of the $m$ AND-gates.
 Then perform the square in the
above equation. We obtain a sum of terms which are constant or
are of the form
$w \cdot \prod_{i \in S'} x_i$, where $w$ is an integer.
Now note that $||S'|| \le 2s$.
Thus the sum is a polynomial $p$ of degree $\le 2s$
with at most $(2^sm+1)^2$ terms, and integer coefficients. We
have that $p \ge 0$, and $p=0$ if and only if $C=1$.

  A similar argument holds for NEQ.
\end{proof}

   We use the following lemma to establish the relativized
separations. It is the same as lemma 30 in \cite{GNW}, translated into
the context of circuits.  In addition, we generalize
the lemma so that it can be applied to Boolean functions which are
 symmetric with respect to certain (disjoint) subsets of the input 
variables, a
generalization of the usual definition of symmetric function.
More precisely, 
   in the following, for any subset $S \subseteq \{x_1,...,x_n\}$ we define,
for any truth assignment to the $x$'s, $y(S) = ||\{j|(x_j \in S) \AND
(x_j=1)\}||$. For some Boolean function $f$ over the variables
$\{x_1,...,x_n\}$, suppose there exist disjoint
subsets $S_1, S_2, ...,S_k \subseteq \{x_1,...,x_n\}$ such that
if we put $y_j = y(S_j)$ for each
$j, 1 \le j \le k$, then $f$ can be expressed as a function $g$ of the
numbers $y_j$, that is, there is a function $g$ such that
 $(\forall x_1,...,x_n) (f(x_1,...,x_n) = g(y_1,...,y_k)).$
We then say that $f$ is {\sl symmetric} in the subsets $S_1,...,S_k$ via the
function $g(y_1,...,y_k)$.

   Tarui (\cite{Taruisep}, proposition 1) proves a similar lemma for
$k=1$ using algebraic techniques. He proves that a polynomial of
degree $d$ which equals 0 for more than $d$ values of $y_1$
identically vanishes for all $y_1$.

\begin{lemma}\label{le:tech}
  Let $s, k, n \in \nat$.
Let $f : \{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function over
the variables $\{x_1,...,x_n\}$ which is symmetric in the
subsets $S_1,...,S_k \subseteq \{x_1,...,x_n\}$ via the function
$g(y_1,...,y_k)$. Let $Y_1, Y_2,...,Y_k$ respectively
denote the sets of values of $y_1,...,y_k$ such that $g(y_1,...,y_k) = 1$,
and suppose that for all $i, 1 \le i \le k$, $||Y_i|| \ge s$.
Let $C$ be an EQ circut of order $< s/2$ such that
$f(x_1,...,x_n)=1 \Rightarrow C=1$.
Then for any input setting, $C=1$.
\end{lemma}

\begin{proof} 
By proposition ~\ref{le:normalize},
 we know that $C$ is computable by a non-negative polynomial $q$
of degree less than $s$.
Let $q$ consist
of terms $c_i$, $i = 1,...,m$, each of degree at most $s-1$.
Let $x$ denote $\{x_1,...,x_n\}$.
Thus $q$ is of the form $\sum_{l=1}^m w_l c_l(x)$ where
the $w_l$'s are integers. We know $C=1$ if and only if
$q(x) = 0$.
 Also from proposition ~\ref{le:normalize} we can assume that
$q(x) \ge 0$ for any setting
of the inputs. We know for any choice of $y_j$'s such that
$g(y_1,...,y_k)=1$, that $q(x) = 0$.
Let us compute the sum of $q(x)$ over input settings $x$
for any fixed $y_j, 1 \le j \le k$. Let the notation ``$x:y$" denote that
the assignments $x$ can vary given fixed values for the $y_j$'s.
One can reverse the order of the sums:
$\sum_{x:y} q(x) =
  {\sum \limits_{l=1}^m {w_l \sum_{x:y} c_l(x)}}$.
Let $S_{lj} = \{i|x_i \in S_j $ and $x_i$ is an input to $c_l\}$ and
$s_{lj} = ||S_{lj}||$. Thus for each $l$,
    $c_l(x) = \prod_{j=1}^k (\prod_{i \in S_{lj}} x_i)$.
Letting $n_j = ||S_j||$ where $1 \le j \le k$,
it is not hard to show that
$$ {\sum \limits_{x:y} {\em c_l(x)}} = 
      {\prod \limits_{j=1}^{k}{{n_j-s_{lj}} \choose {y_j-s_{lj}}}}. $$
Observe that, by hypothesis, $\sum_{j=1}^k s_{lj} < s$,
so that the quantity
$${\prod \limits_{j=1}^{k} {y_j!(n_j-y_j)!}}
  {\prod \limits_{j=1}^{k}{{n_j-s_{jl}} \choose {y_j-s_{jl}}}}
  =
  {\prod \limits_{j=1}^k
     [(n_j-s_{jl})!{\prod \limits_{i=0}^{s_{jl}-1} {(y_j-i)}]}} $$
is a polynomial in each individual $y_j$ of degree $< s$.
Therefore the quantity
$${\prod \limits_{j=1}^{k} {y_j!(n_j-y_j)!}}
  {\sum \limits_{x:y} {q(x)}}$$
is a polynomial $p(y_1,...,y_k)$ of degree $< s$ in each $y_j$.
Since for any $x$ such that $g(y_1,...,y_k)=1$ we
also have $q(x) = 0$, it follows from the definition of
$p(y_1,...,y_k)$ that $p(y_1,...,y_k)=0$ for any
such $x$. Conversely, note that since $q(x) \ge 0$ for any $x$, if for 
any
choice of $y_1,...,y_k$ we have $p(y_1,...,y_k)=0$, then for all $x$ with
this choice of $y_1,...,y_k$, it follows that $q(x) = 0$ and therefore
$C=1$.

 We will now show that for all possible values of $y_1,...,y_k$,
$p(y_1,...,y_k) = 0$. This will prove that for all input settings, $C=1$.

 We know by hypothesis that
$$(\forall y_1 \in Y_1)(\forall y_2 \in Y_2)...(\forall y_k \in Y_k)
  (g(y_1,...,y_k) = 1).$$
where for all
$i, 1 \le i \le k$, $||Y_i|| \ge s$. Thus from the above
argument, it follows that
$$(\forall y_1 \in Y_1)(\forall y_2 \in Y_2)...(\forall y_k \in Y_k)
  (p(y_1,...,y_k) = 0).$$
Fix any $y_1, y_2,...,y_{k-1}$ to the values
${\rm y}_1, {\rm y}_2,...,{\rm y}_{k-1}$ respectively where
${\rm y}_1 \in Y_1, {\rm y}_2 \in Y_2,...$
and ${\rm y}_{k-1} \in Y_{k-1}$ (the Roman y's denote that these values
are fixed). Then $p({\rm y}_1,...,{\rm y}_{k-1},y_k)$ is a polynomial
in $y_k$ of degree $< s$. However,
$g({\rm y}_1,...,{\rm y}_{k-1},y_k) = 1$ for
$\ge s$ values of $y_k$, and hence $p({\rm y}_1,...,{\rm y}_{k-1},y_k)=0$
for this many values of $y_k$. Therefore
$p({\rm y}_1,...,{\rm y}_{k-1},y_k) = 0$ for
all values of $y_k$, $0 \le y_k \le ||S_k||$. Proceeding inductively
in this fashion, we find that
$$(\forall y_1, 0 \le y_1 \le ||S_1|| )...(\forall y_k, 0 \le y_k \le ||S_k||)
  (p(y_1,...,y_k) = 0).$$
This proves the lemma.
\end{proof}

  Note that we can replace ``EQ" with ``NEQ" and ``$C=1$" with ``$C=0$" in
the above lemma and that it remains true.

  Lemma ~\ref{le:tech}
will be used to eliminate EQ (respectively, NEQ) circuits by showing
that they have constant values.

\section{Separations of P$^{\rm \bf C_=P}$
           from P$^{\rm \bf PP}$}

    As explained in the introduction, intuitively PP appears to be more
powerful than $\EP$ in deterministic reductions, even though it is no
more powerful than $\EP$ in nondeterministic reductions. We
show here that any proofs that Turing reductions to $\EP$ are as powerful
as Turing reductions to $\PP$ would, at least, not relativize.
 These separations leave open the possibility that,
while $\P^{\PP}$ machines can count (via the binary search technique
mentioned in the introduction), $\P^{\EP}$ perhaps cannot.

   First we need an alternative characterization of $\P^{\EP}$ in terms of
the extended Boolean hierarchy over $\EP$. Following
Wagner \cite{Wagnerrecent}, we define, for any complexity class ${\cal 
C}$ and
for any bounding
 function $b$, the class ${\cal C}(b)$
as follows: $A \in {\cal C}(b)$ if and only if there exists a $B \in {\cal C}$
such that for any $x$, for all $z$ where $1 \le z \le b(|x|)$,
        $\chi_B(\langle x,z\rangle) \le \chi_B(\langle x,z-1\rangle)$,
and $x \in A$ if and only if
  $max \{z| 0 \le z \le b(|x|)-1$ and $\langle x,z\rangle \in B\}$ is odd.
${\cal C}(2^{poly})$ is defined as $\bigcup_{c \in \nat} {\cal C}(2^{n^c})$.
It was shown in \cite{Wagnerrecent}
 that $\NP(2^{poly}) = \P^{\NP}$. We can prove the
analogous result here.

\begin{theorem}\label{le:characterization}
$\coEP(2^{poly}) = \P^{\EP}$.
\end{theorem}
\begin{proof}
($\subseteq$): Let $A \in \coEP(2^{poly})$ and let $B$ be as in the
definition above (with ${\cal C} = \coEP$),
and $b$ the bounding function (of the form $2^{p(n)}$).
Define the set
   $S = \{\langle x,y\rangle| 0 \le y \le b(|x|),
              (\exists z, 0 \le z \le b(|x|))
                (z > y \AND \langle x,z\rangle \in B)\}$.
By binary search, we can find the maximum $y$ such that
    $\langle x,y \rangle \in S$ in time $p(|x|)$, using
$S$ as an oracle. We can easily
tell if the maximum $y$ is odd. Finally, note that $S \in \exists \coEP
= \coEP$. Then $A \in \P^{\EP}$.

($\supseteq$): Let $L \in \P^{\EP}$ via machine $M$ which makes queries
to a set $A \in \coEP$. Define the set $B'$ as follows.
$B'= \{\langle x,z \rangle | z=r_1\#r_2\#...r_{p(|x|)}\#a,
           a \in \{0,1\},M$, using query answers
               $r_1,...,r_{p(|x|)}$, produces queries
               $q_1,...,q_{p(|x|)}$, and $(M$ accepts $x \Iff a=1)\AND
                   (\forall i)(r_i=1 \Rightarrow q_i \in A)\}$.
Using the fact that $\coEP$ is closed under conjunctive truth-table
reductions, it is easy to see that $B' \in \coEP$. Furthermore,
$M$ accepts $x$ if and
only if the maximum $z$ such that $\langle x,z \rangle \in B'$ is odd.
Thus
\begin{eqnarray*}
  x \in L & \Iff & max\{z| \langle x,z \rangle \in B'\} \not = 0~\mod~2\\
          & \Iff & max\{z| (\exists w \ge z)
                            \langle x,w \rangle \in B'\} \not = 0~\mod~2\\
          & \Iff & max\{z| \langle x,z \rangle \in B\} \not = 0~\mod~2
\end{eqnarray*}
where $B = 
   \{\langle x,z\rangle| (\exists w \ge z)(\langle x,w \rangle \in B')\}$.
Now since $B' \in \coEP$, $B \in \exists \coEP = \coEP$. Furthermore,
$\chi_B(\langle x,z \rangle) \le \chi_B(\langle x,z-1 \rangle)$. This
proves the theorem.
\end{proof}

  Observe that the statement
    $max\{z| \langle x,z \rangle \in B\} \not = 0~\mod~2$
is equivalent to the statement
    $\sum \limits_{z=0}^{b(|x|)} {\chi_B(\langle x,z \rangle)} \not = 0
                   ~\mod~2$,
because of the monotonicity of the $\chi_B$'s in $z$. Thus the separation
results can be understood in terms of a simple and highly constrained
circuit model.

\begin{definition}\label{le:circuits}
Let $c_i$, $1 \le i \le m$, be a set of NEQ circuits, 
over the inputs $\{x_1,...,x_n\}$, each of order $s$, with the
property that $c_i = 1 \Rightarrow c_{i-1} = 1$.
 A $\P^{\EP}$-{\sl circuit of size} $m$ {\sl and order} $s$
is a circuit which outputs 1 if
and only if $||\{i|1 \le i \le m, c_i=1\}||$ is odd.
\end{definition}

\begin{proposition}\label{le:reduction}
 Let $M$ be a $\P^{\EP^A}$-machine. Then there is a polynomial
$q$ such that for any input $x$,
there exists a $\P^{\EP}$-circuit $C$ of order $q(|x|)$
 whose inputs are of the form $\chi_A(z)$ ($|z| \le p(|x|)$),
such that $C=1$ if and only if $M$ accepts $x$.
\end{proposition}
\begin{proof}
  By theorem ~\ref{le:characterization}
 and the remarks following it, we can assume there is a set
$B \in \coEP^A$ and a polynomial $p$ such that for any $x$, $M$ accepts 
$x$
if and only if
$${ \sum \limits_{z=0}^{2^{p(|x|)}} {\chi_B(\langle x,z \rangle)}}
    \not = 0 ~\mod~2.$$
Let $N$ be a $\coEP^A$ machine with time bounded by polynomial $r$,
recognizing $B$, so that for some
$t \in \FP$, for any $x$, $x \in B$ if and only if
$\#acc_N(x) \not = t(x)$. Note that for some polynomial $q$,
$r(|\langle x,z \rangle|) \le q(|x|)$, so that computation paths
of $N$ on input $\langle x,z \rangle$ are no longer than $q(|x|)$.
Because $N$ correctly recognizes $B$, it is clear that if
$N$ accepts on input $\langle x,z \rangle$ then $N$ also accepts on input
$\langle x,z-1 \rangle$. Consider the computation of $N$ on an
input $\langle x,z \rangle$. In a standard fashion,
define a new machine $N'$ which simulates
$N$ as follows. Whenever $N$ would query a string to $A$, $N'$
guesses an answer and records both the query and the guess.
When $N'$ arrives in an accept state of $N$, it attempts to verify
the answers it guessed by making queries to $A$ in a series of
universal moves; refer to the resulting subtree as a ``verification
subtree". Note that the verification subtrees are no larger than
$q(|x|)$.
Also note that $N'$ may have as many as $2^{2q(|x|)}$ computation
paths leading to verification subtrees
(the upper bounded applying if $N$ made queries in every
step of every computation path). Now we can think of the computation
tree of $N'$ on input $\langle x,z \rangle$
as an NEQ circuit which (for any given $x$) we will
call $c_z$. The inputs to $c_z$ are values of the characteristic
function of $A$ for various strings (i.e., of the form $\chi_A(w)$).
The verification subtrees correspond to AND-gates with fanin $q(|x|)$.
We eliminate the contribution of
computation paths along which no queries were made by adjusting
the threshold. If $a_{nq}$ is the number of
accepting paths of $N$ along which no queries were made,
then the threshold for $c_z$ will be $t(x) - a_{nq}$.
Thus for any input to $N$ of the form $\langle x,z \rangle$,
$c_z$ outputs 1 if
and only if $N$ accepts. Furthermore, each $c_z$ is of order
$q(|x|)$.

Evidently $M$ accepts $x$ if and only if
$${ \sum \limits_{z=0}^{2^{p(|x|)}} c_z} \not = 0 ~\mod~2$$
and furthermore $c_z=1 \Rightarrow c_{z-1}=1$. This defines
a $\P^{\EP}$-circuit of order $q(|x|)$. Note that this order is
polylogarithmic in the
number of inputs to the circuit, since the number of inputs
(which are of the form $\chi_A(w)$ where $|w| \le q(|x|)$) is
exponential in $|x|$.
\end{proof}

  In the proof of the following we make use of lemma ~\ref{le:tech},
restricted to the case of $k=1$, that is, for ordinary symmetric functions.
  We say a family of circuits $\{C_n\}$ has {\sl polylog order} if
there exists a polynomial
$q$ such that for all $n$, $C_n$ has order $q(log(n))$.

\begin{lemma}\label{le:p-separation-lemma}
Let $s \in \nat$, $s \ge 1$, and $f : \{0,1\}^n \rightarrow \{0,1\}$ be a
symmetric Boolean function such that if
 we put $y=||\{i | x_i=1\}||$, then $f(x_1,...,x_n)=1$ for
 $\ge s$
values of $y$ and $f(x_1,...,x_n)=0$ for $\ge s$ values of $y$. Then no
$\P^{\EP}$-circuit $C$ of order $< s/2$ can compute $f$.
\end{lemma}
\begin{proof}
    Let $C(x_1,...,x_n)$ be a $\P^{\EP}$-circuit of order $< s/2$
with NEQ subcircuits
$c_i, 1 \le i \le m$, which computes
$f(x_1,...,x_n)$. We will show that for all input settings, $C=0$.
  Suppose the number of NEQ subcircuits $m$ is odd (the proof when $m$
is even is the same, as will be obvious). Then whenever $f(x) = 0$,
we must have $c_m = 0$, since if $c_m = 1$ all the $c_i$'s with $i < m$
will also have to be 1, and hence we would have $C=1$.
By hypothesis, for $\ge s$ values of $y$, $f(x)=0$.
Since $c_m$ is of order $< s/2$ but is zero for
$\ge s$ values of $y$, we can conclude from
lemma ~\ref{le:tech} that $c_m = 0$ for all input settings.
This eliminates $c_m$ from consideration.
Consider the remaining $m-1$ gates. Since $m-1$ is even, if $f(x)=1$
 we must
have $c_{m-1}=0$, otherwise an even number of NEQ circuits would yield 1.
$c_{m-1}$ can be eliminated just as $c_m$, since $f(x)=1$ for 
$\ge s$ values
of $y$. Proceeding inductively, we find
that all the $c_i$'s equal 0 for all input settings, and therefore $C=0$
for all input settings.
\end{proof}

  The parity function on $n$ inputs,
$\PARITY(x_1,...,x_n) = $, is defined to be
1 if and only if $||\{i|x_i=1\}||$ is odd.

\begin{lemma}\label{le:parity-separation-lemma}
For any $n \ge 1$, no $\P^{\EP}$-circuit of order $< n/4$
can compute the parity function on $n$ inputs.
\end{lemma}
\begin{proof}
  $\PARITY(x_1,...,x_n)$ is a symmetric function which is 1 for $\ge n/2$
values of $y=||\{i|x_i=1\}||$ and is 0 for $\ge n/2$ values of $y$.
Applying lemma ~\ref{le:p-separation-lemma}, the result is immediate.
\end{proof}

 In the proof of the following, as well as in the following section,
$s_i^n$ denotes the $i^{\rm th}$ string of length $n$. We note that
Tarui \cite{Taruisep} has independently obtained the theorem
as well as theorem ~\ref{le:bpp-separation}
using slightly different techniques. In place of the concept of
$\P^{\EP}$-circuits, Tarui uses the concept of small-depth
decision trees.

\begin{theorem}\label{le:parity-separation}
There exists an oracle $A$ such that $\PARITYP^A \not \subseteq 
\P^{\EP^A}$.
\end{theorem}
\begin{proof}
  Define the test language
      $L(A) = \{1^n| $ there are an odd number of strings in $A$
                        of length $ n\}$. Then $L(A) \in \PARITYP^A$
for any $A$. Thus for any $n$, $1^n \in L(A)
\Iff \PARITY(\chi_A(s^n_1),\chi_A(s^n_2),...,\chi_A(s^n_{2^n})) = 1$.
An $A$ can be constructed in stages such that
$L(A) \not \in \P^{\EP^A}$. Let $M_i, i \in \nat$ be an enumeration
of $\P^{\EP}$-machines. At stage i, we will choose an
$n_i \in \nat$. We know that from proposition ~\ref{le:reduction},
there is a polynomial
$q_i$ such that we can find a $\P^{\EP}$-circuit
of order $q_i(n_i)$ which outputs 1 if and only if $M_i$ accepts
$1^{n_i}$. We choose $n_i$ to be
$\ge$ its value in the previous stage and sufficiently large
that $q_i(n_i) < 2^{n_i-2}$. Using lemma ~\ref{le:parity-separation-lemma}
one can easily show that it is
possible to add strings to $A$ of length $n_i$ such that
$1^{n_i} \in L(A) \Iff M_i$ rejects
$1^{n_i}$. Strings not of length $n_i$ which $M_i$ queries
at this stage, unless fixed at earlier stages, are not put
in $A$. We then set $n_{i+1}$ to the smallest integer greater
than any of the strings queried by $M_i$ and proceed to stage
$i+1$.
\end{proof}

Using the same technique it is also possible to prove that in some
relativized world the polynomial hierarchy is not contained in $\P^{\EP}$.
In fact we can construct an oracle such that BPP is not contained in
$\P^{\EP}$, which provides a simultaneous proof that there is an oracle
such that neither $\Sigma_2^p \cap \Pi_2^p$ nor $\PP$ are contained in
$\P^{\EP}$.
For this purpose we define a function related to BPP.
Define the ``strict majority" function on $n$ inputs $\Tmaj$ as follows:
\[ \Tmaj(x_1,...,x_n)  = 
   \left\{ \begin{array}{ll}
             1 & \mbox{if ${\sum_{i=1}^n x_i} \ge {3 \over 4}n$,} \\
             0 & \mbox{if ${\sum_{i=1}^n x_i} \le {1 \over 4}n$,} \\
             ? & \mbox{otherwise.}
\end{array} \right. \]

We say a circuit $C$ {\sl computes} $\Tmaj$
if $\Tmaj(x_1,...,x_n)=1 \Rightarrow C(x_1,...,x_n)=1$ and
   $\Tmaj(x_1,...,x_n)=0 \Rightarrow C(x_1,...,x_n)=0$.

\begin{lemma}\label{le:bpp-separation-lemma}
 For any $n \ge 1$, no $\P^{\EP}$-circuit of order $< n/8$ can
compute the strict majority function on $n$ inputs.
\end{lemma}
\begin{proof}
  $\Tmaj(x_1,...,x_n)$ is a symmetric function which is 1 for $\ge n/4$
values of $y=||\{i|x_i=1\}||$ and is 0 for $\ge n/4$ values of $y$.
The result follows from lemma ~\ref{le:p-separation-lemma}.
\end{proof}

\begin{theorem}\label{le:bpp-separation}
There exists an oracle $A$ such that $\BPP^A \not \subseteq \P^{\EP^A}$.
\end{theorem}
\begin{proof}
  Define the test language
    $L(A) = \{1^n| $ at least 3/4 of the strings of length $n$ are
                     in $A \}$.
Clearly, for any $A$ such that for each length $n$, either 3/4 of the
strings of that length are in $A$ or no more than 1/4 are in $A$, then
$L(A) \in \BPP^A$. For such $A$'s,
 $\Tmaj(\chi_A(s_1^n),\chi_A(s_2^n),...,\chi_A(s_{2^n}^n))=1 \Iff
  1^n \in L(A)$
and
 $\Tmaj(\chi_A(s_1^n),\chi_A(s_2^n),...,\chi_A(s_{2^n}^n))=0 \Iff
  1^n \not \in L(A)$.
The proof is a stage construction as in theorem ~\ref{le:parity-separation}.
 Let $M_i, i \in \nat$ be an enumeration
of $\P^{\EP}$-machines. Analogously to the proof of theorem
~\ref{le:parity-separation}, using lemma ~\ref{le:bpp-separation-lemma}
 one can easily show that $A$ can
be constructed such that for each $i$, for some $n_i$,
$1^{n_i} \in L(A) \Iff M_i$ rejects
$1^{n_i}$, and furthermore
$\Tmaj(\chi_A(s^{n_i}_1),\chi_A(s^{n_i}_2),...,\chi_A(s^{n_i}_{2^{n_i}}))=1
\Iff 1^{n_i} \in L(A)$
and
 $\Tmaj(\chi_A(s^{n_i}_1),\chi_A(s^{n_i}_2),...,\chi_A(s^{n_i}_{2^{n_i}}))=0
\Iff 1^{n_i} \not \in L(A)$.
\end{proof}

\begin{corollary}\label{le:ph-separation}
There exists an oracle $A$ such that $\Sigma_2^{p,A} \cap \Pi_2^{p,A}
\not \subseteq \P^{\EP^A}$ and $\PP^A \not \subseteq \P^{\EP^A}$.
\end{corollary}
\begin{proof}
  It is well known that $\BPP \subseteq \PP \cap \Sigma_2^p \cap 
\Pi_2^p$
via a proof that relativizes (e.g., \cite{Lauten}).
\end{proof}

\section{An Oracle Interlocking the Query Hierarchies Over NP and
 C$_=$P}

    In this section we construct an oracle which gives an optimal
separation of the Boolean and query hierarchies over $\NP$ and $\EP$.
This represents a technical improvement of the oracle of Gundermann,
Nasser and Wechsung \cite{GNW}.

 It is possible to reduce this separation to circuit lower bounds. We
now give this reduction.

   Define the function $f_{2k,n}$ in $2kn$ variables
$X = \{x_{ij} | i = 1..n, j = 1..2k\}$ as follows:
\begin{eqnarray*}
  f_{2k,n}(X) = {\bigvee \limits_{j=1}^k 
                 {[({\bigvee \limits_{i=1}^n {x_{i,(2j-1)}}}) \AND
                   ({\bigwedge \limits_{i=1}^n {{\overline x}_{i,2j}}})]}}
\end{eqnarray*}

  Similarly, we define $f_{2k+1,n}(X \cup \{x_{i,2k+1}\})$ as
\begin{eqnarray*}
  f_{2k+1,n}(X \cup \{x_{i,2k+1}\}) = f_{2k,n}(X)
                  \OR ({\bigvee \limits_{i=1}^n {x_{i,2k+1}}})
\end{eqnarray*}

   Observe that $f_{k,n}$ is symmetric in the subsets $S_j = \{x_{ij} |
1 \le i \le n \}$, where $1 \le j \le k$, via the following function $g$:
Setting $y_j = ||\{i | x_{ij}=1 \}||$, when $k$ is even,
$g(y_1,...,y_k)=1$ if and only if for some odd $j \le k-1$ we have $y_j > 0$ 
and
$y_{j+1} = 0$. When $k$ is odd, $g(y_1,...,y_k)=1$ if and only if
 $y_k > 0$ or
for some odd $j \le k-2$ we have $y_j > 0$ and $y_{j+1} = 0$.

  A $\BH_k^{\EP}$ circuit is defined inductively as follows. A 
$\BH_1^{\EP}$ circuit is an EQ circuit.
 A $\BH_{2k}^{\EP}$ circuit is a circuit of the
form $C_1 \OR C_2$ where $C_1$ is a $\BH_{2k-1}^{\EP}$ circuit and 
$C_2$ is an NEQ circuit. A $\BH_{2k+1}^{\EP}$ circuit is a circuit of the form
$C_1 \AND C_2$ where $C_1$ is a $\BH_{2k}^{\EP}$ circuit and $C_2$ is an
EQ circuit. A $\BH_k^{\EP}$ circuit of order $s$ is one
in which the base EQ and NEQ circuits are all of order $s$.

  The main theorem which allows a complete separation of $\BH(\NP)$ 
from $\BH(\EP)$ is the following.
It is here that we use the full power of lemma ~\ref{le:tech}, with
arbitrary $k$.

\begin{theorem}\label{le:separation-theorem}
For any $n \ge 1$ and $k \ge 1$, no $\BH_k^{\EP}$ circuit
$C$ of order $< n/2$ can compute $\{f_{k,n}\}$.
\end{theorem}
\begin{proof} For convenience in the proof we drop the $n$
subscript in $f_{k,n}$.
The proof is by induction. For the base
case, suppose $f_1$
is computable by a $\BH_1^{\EP}$ circuit, i.e., an EQ circuit $C^0$,
of order $< n/2$. Define $y_1 = ||\{i | x_{i,1} = 1 \}||$. We know that if
$y_1 > 0$ then $C^0=1$. Thus $C^0=1$ for $n$ values
of $y_1$, and hence by
lemma ~\ref{le:tech}, for all input settings $C^0=1$. However then
$C^0=1$ when $f_1=0$, a contradiction.

  For the inductive step, we first consider even levels. Suppose by
hypothesis that no $\BH_{2k-1}^{\EP}$-circuit of order $< n/2$
can compute $f_{2k-1}$.
Suppose however that there exists a $\BH_{2k}^{\EP}$-circuit
$C$ of order $< n/2$ to
compute $f_{2k}$ correctly. $C$ is of the form $C_1 \OR C_2$, where
$C_1$ is a $\BH_{2k-1}^{\EP}$-circuit and $C_2$ is an NEQ circuit,
both of order $< n/2$.
Let $y_j = ||\{i | x_{ij} = 1\}||$, as in the discussion preceeding
this theorem. Also note from that discussion that whenever $y_j > 0$
for all EVEN $j$, $f_{2k}=0$.
Since for all $j$, $0 \le y_j \le n$, the function $g(y_1,...,y_{2k})$ is
zero for $n$ values of $y_1,...y_{2k}$, respectively. Now
whenever $g(y_1,...y_{2k}) = 0$, $C_2 = 0$. Then by lemma ~\ref{le:tech},
for all input settings $C_2=0$. We can thus ignore $C_2$.
By setting $y_{2k}=0$, we find that $C_1$ computes
$f_{2k-1}$ correctly, which
contradicts the induction hypothesis.

The argument for odd values $2k+1$ is similar to the base case. We assume
by hypothesis that no $\BH_{2k}^{\EP}$-circuit of order $< n/2$
can compute $f_{2k}$, but
that there exists a $\BH_{2k+1}^{\EP}$-circuit of order $< n/2$
of the form $C_1 \AND  C_2$
which computes $f_{2k+1}$ correctly. We
define as before $y_j = ||\{i | x_{i,j} = 1\}||$, $1 \le j \le 2k+1$,
now noting that whenever $y_{2k+1} > 0$ we have $f_{2k+1} = 1$. As
before we find that for all input settings $C_2 = 1$,
and by setting $y_{2k+1} = 0$ we conclude that $C_1$ computes $f_{2k}$
correctly, which is a contradiction.
\end{proof}

   The next proposition establishes the relationship between
$\BH_k(\EP^A)$ and $\BH_k^{\EP}$-circuits.

\begin{proposition}\label{le:bh-reduction}
   Let $k \ge 1$. For any $\BH_{2k-1}(\EP^A)$ machine $M$, there
is a polynomial $q$ such that for any input
$x$ there exists a $\BH_{2k-1}^{\EP}$-circuit $C$ of order $q(|x|)$
with inputs $\chi_A(w)$,
$|w| \le q(|x|)$, and $C=1$ if and only if $M$ accepts $x$.
Similarly, for any $\coBH_{2k}(\EP^A)$ machine $M$, there
is a polynomial $q$ such that for any input
$x$ there exists a $\BH_{2k}^{\EP}$-circuit $C$ of order $q(|x|)$
with inputs $\chi_A(w)$,
$|w| \le q(|x|)$, and $C=1$ if and only if $M$ accepts $x$.
\end{proposition}
\begin{proof}
   The proof is by induction. For $k=1$, it is easy to show (as in
the proof of proposition ~\ref{le:reduction}) that for any
$\EP^A$ machine $M$ and input $x$, there exists an EQ circuit
$C$ such that $M$ accepts $x$ if and only if $C=1$. The order of the circuit
is polynomial in $|x|$. (Note that since there are exponentially many inputs 
of the form $\chi_A(w)$, the order is polylog in the number of inputs to $C$.)

   Suppose the proposition is true for some $k \ge 1$. Consider any
 $\coBH_{2k}(\EP^A)$-machine $M$. By proposition ~\ref{le:normal-form-2},
 there exist a $\BH_{2k-1}(\EP^A)$-machine $M_1$ and a $\coEP$-machine
$M_2$ such that for any input $x$, $M$ accepts $x$ if and only if either
$M_1$ or $M_2$ accept $x$. By the induction hypothesis, we can replace
$M_1$ with a $\BH_{2k-1}^{\EP}$-circuit $C_1$ of order polynomial in $|x|$.
By an argument similar to
the base case, we can replace $M_2$ with an NEQ circuit $C_2$ of order
polynomial in $|x|$.
This yields a circuit of the form $C_1 \OR C_2$ which outputs 1 if and 
only
if $M$ accepts $x$. $C_1 \OR C_2$ is a $\BH_{2k}^{\EP}$ circuit of
order polynomial in $|x|$. The
argument that we can find an appropriate $\BH_{2k+1}^{\EP}$-circuit
for any $\BH_{2k+1}(\EP^A)$-machine is similar, again using
proposition ~\ref{le:normal-form-2}.
\end{proof}

  We are now in a position to explain how the oracle separations follow
from theorem ~\ref{le:separation-theorem}.
 Define, for each $k$, the test languages $L_k(A)$ related to the
functions $f_{k,n}$ as follows.
$$ L_{2k}(A) = \{1^n| 
                   {\bigvee 
                     \limits_{i=1}^k
                       {[(\exists z,|z|=n)(\langle z,2i-1 \rangle \in A)
                         \AND
                         (\forall z,|z|=n)(\langle z,2i \rangle \not \in A)]}}
                \} $$
$$ L_{2k+1}(A) = \{1^n| 
                   1^n \in L_{2k}(A)
                   \OR
                   [(\exists z, |z|=n)(\langle z, 2k+1 \rangle \in A)]
                \} $$\\
 It is clear from proposition ~\ref{le:normal-form-1}
that for all $k$ and $A$, $L_k(A) \in \BH_k(\NP^A)$. Furthermore,
for any $x$, $x \in L_k(A) \Iff f_{k,2^n}(X(A)) = 1$ where the arguments
$X(A)$ for $f_{k,2^n}$ are defined by $x_{i,j} =
 \chi_A(\langle s_i^n,j \rangle)$.

Combining these observations with theorem ~\ref{le:separation-theorem}
proposition ~\ref{le:bh-reduction}, and a stage construction such as
in theorem ~\ref{le:parity-separation}, we conclude that for some $A$,
for all even $k$,
$L_{k}(A) \not \in \coBH_k(\EP^A)$, and for all odd $k$,
$L_{k}(A) \not \in \BH_k(\EP^A)$. This proves

\begin{theorem}\label{le:bh-separation}
There exists an oracle $A$ such that for odd $k$,
$\BH_k(\NP^A) \not \subseteq \BH_k(\EP^A)$ and for even $k$,
$\BH_k(\NP^A) \not \subseteq \coBH_k(\EP^A)$.
\end{theorem}

  Then using theorem ~\ref{le:intertwining}, we have,

\begin{corollary}\label{le:qh-separation}
There exists an oracle $A$ such that
$\P_{(k+1)-\T}^{\NP^A} \not \subseteq \P_{k-\T}^{\EP^A}$.
\end{corollary}

\section{Open Problems}
   Oracle separations are naturally not satisfying in these times of
techniques that do not relativize (see, e.g., \cite{Babai} and
references therein), and thus the results of this paper
raise more questions than they answer. It would be interesting to see
sharper results along the lines of Theorem ~\ref{le:collapse-1},
in particular using techniques which exploit {\sl differences} rather
than similarities between NP and $\coEP$ (indeed, it is possible
that Theorem ~\ref{le:collapse-1} is trivial since it is possible with our
current state of knowledge that $\P^{\PP} = $PSPACE). Similarly, some 
plausible
separation of $\P^{\EP}$ from $\P^{\PP}$ without oracles would be
very interesting: Does the hypothesis $\P^{\EP} = \P^{\PP}$ have
any dramatic consequences?\\

\noindent{\bf Acknowledgements}

  I wish to thank the members of the
Departament de Llenguatges i Sistemes Inform{\`a}tics,
UPC Barcelona,
where this work was done, for their hospitality, with special thanks
to Jos{\'e} Balc{\'a}zar for helping to make the visit possible and for
valuable suggestions and comments on the paper.
I thank Jacobo Tor{\'a}n for suggestions as well as
many discussions on this subject,
and Mitsunori Ogiwara and Seinosuke Toda 
for sharing their results with me.
Conversations with Antoni Lozano and
Gerd Wechsung are also gratefully acknowledged. I am grateful
to two anonymous referees who pointed out some errors in the
original version of this paper and
made many suggestions which greatly improved the presentation.
 
\begin{thebibliography}{1}

\bibitem{Babai}
L.~Babai, ``E-Mail and the Unexpected Power of Interaction",
{\em 5th Annual Conference on Structure in Complexity Theory} (1990)
30-44.

\bibitem{BB}
A.~Bertoni, D.~Bruschi, D.~Joseqh, M.~Sitharam, and P.~Young,
``Generalized Boolean Hierarchies and Boolean Hierarchies over
RP", {\em Proceedings of the 7th Conference on Fundamentals
of Computation Theory}, Springer-Verlag 1989,
Lecture Notes in Computer Science 380.
 
\bibitem{BDG}
J.~L.~Balc{\'a}zar, J.~D{\'\i}az, and J.~Gabarr{\'o}, {\em Structural
Complexity Theory I}, Volume II of {\em EATCS Monographs on Theoretical
Computer Science}, Springer-Verlag, New York, 1988.

\bibitem{Bei}
R.~Beigel, ``Bounded Queries to SAT and the Boolean Hierarchy", Johns
Hopkins Tech Report 87-8 (1988), to appear in Theoretical Computer 
Science.

\bibitem{BCO}
R.~Beigel, R.~Chang, and M.~Ogiwara, ``A Relationship between
Difference Hierarchies and Relativized Polynomial Hierarchies",
manuscript, January, 1991.

\bibitem{BRS}
R.~Beigel, N.~Reingold and D.~Spielman,  ``PP is Closed Under Intersection",
STOC 1991.

\bibitem{BussHay}
S.~R.~Buss and L.~Hay, ``On Truth-table Reducibility to SAT and the
Difference Hierarchy Over NP", {\em Proceedings of the 3rd Conference
on Structure in Complexity Theory} (1988) 224-233.

\bibitem{Cai}
J.-y.~Cai ``Probability One Separation of the Boolean Hierarchy",
{\em 4th Annual Symposium on Theoretical Aspects of Computer Science},
Springer-Verlag Lecture Notes in Computer Science 247 (1987) 148-158.

\bibitem{Caietal}
J.-y.~Cai, T.~Gunderman, J.~Hartmanis, L.~A.~Hemachandra, V.~Sewelson,
K.~Wagner, and G.~Wechsung, ``The Boolean Hierarchy I: Structural 
Properties",
{\em SIAM Journal of Computing}, {\bf 17} (1988) 1232-1252.

\bibitem{Hem}
L.~A.~Hemachandra, ``The Strong Exponential Hierarchy Collapses",
{\em Journal of Computer and System Science} (1989) 299-322.

\bibitem{KC}
R.~Chang and J.~Kadin, ``The Boolean Hierarchy and the Polynomial
Hierarchy: a Closer Connection", {\em 5th Annual Conference on Structure
in Complexity Theory} (1990) 169-178.

\bibitem{GNW}
T.~Gundermann, N.~A.~Nasser and G.~Wechsung, ``A Survey on Counting 
Classes",
{\em 5th Annual Conference on Structure in Complexity Theory} (1990)
140-153.

\bibitem{K}
J.~Kadin, ``Restricted Turing Reducibilities and the Structure of the
Polynomial Time Hierarchy", Ph.D. thesis, Cornell University, February
1988.

\bibitem{Lauten}
 C.~Lautenmann, ``BPP and the Polynomial Hierarchy", {\em Information
Processing Letters} {\bf 17} (1983) 215-217.

\bibitem{Ogiwara}
M.~Ogiwara, ``Generealized Theorems on Relationships Among Reducibility
Notions to Certain Complexity Classes", manuscript, April 1991.

\bibitem{Tarui}
J.~Tarui, ``Randomized Polynomials, Threshold Circuits, and the
Polynomial Hierarchy", {\em Proceedings of the 8th Annual Symposium
on Theoretical Aspects of Computer Science} (1991) 238-250.

\bibitem{Taruisep}
J.~Tarui, ``Degree Complexity of Boolean Functions and Its
Applications to Relativized Separations", to appear in {\em 6th Annual
Conference on Structure in Complexity Theory} (1991).

\bibitem{Toda}
S.~Toda, ``On the computational power of $\PP$ and $\PARITYP$", {\em
Proceedings 30th IEEE Symposium on Foundations of Computer Science}
(1989) 514-519.

\bibitem{TodasTalk}
S.~Toda, ``On Polynomial-Time Truth-Table Reducibility to $\EP$ Sets",
Colloquium, Department of Computer Science, University of Chicago,
October 26, 1990.

\bibitem{TO}
S.~Toda and M.~Ogiwara, ``Counting Classes Are as Hard as the Polynomial-
Time Hierarchy", to appear in {\em 6th Annual Conference on Structure in
Complexity Theory} (1991).

\bibitem{ToranThesis}
J.~Tor{\'a}n, ``Structural Properties of the Counting Hierarchy", Ph.D.
thesis, Facultat d'Informatica de Barcelona, 1988.

\bibitem{Toran}
J.~Tor{\'a}n, ``An Oracle Characterization of the Counting
Hierarchy", {\em 3rd Annual Conference on Structure in
Complexity Theory} (1988) 213 - 223.

\bibitem{Wagner}
K.~Wagner, ``Compact Descriptions and the Counting Polynomial Time
Hierarchy", {\em Acta Informatica} {\bf 23} (1986) 325-356.

\bibitem{Wagnerrecent}
K.~Wagner, ``Bounded Query Classes", {\em SIAM Journal of Computing}
{\bf 19} (1990) 833-846.

\end{thebibliography}
 
\end{document}

