% 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}