%mm6/8/99 \documentstyle[12pt]{article} %au queries \newcommand{\query}[1]{\marginpar{\raggedright\scriptsize #1}} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{proposition}{Proposition} \newtheorem{definition}{Definition} \newcommand{\qed}{$\Box$} %MM added \newenvironment{proof} {\begin{trivlist}\item[\hskip\labelsep{\textbf{Proof}}]} {\leavevmode\unskip\nobreak \quad\qed \end{trivlist}} \title{The Permanent Requires Large Uniform Threshold Circuits\footnotetext{A preliminary version of this work appeared in \cite{cj99-07-30}.}} \author{Eric Allender\\ Department of Computer Science\\ Rutgers University\\ Piscataway, NJ 08855-1179\\ {\tt allender@cs.rutgers.edu}\\ {\tt http://www.cs.rutgers.edu/$\tilde{~}$allender/} } \date{6 August 1999} \begin{document} %% %% Generic Titlepage %% \def\registered{\({}^{\ooalign% {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}% \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)} \begin{titlepage} \pagenumbering{roman} \null\vfil\vskip 60pt \begin{center} {\Huge\bf Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science\par} \vskip 3em {\huge\it The MIT Press\par} \end{center} \par\vskip 1.5em {\Large \begin{center} Volume 1999, Article 7\\ \textit{The Permanent Requires Large Uniform Threshold Circuits} \end{center} } \par\noindent ISSN 1073--0486\@. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; \emph{journals-orders@mit.edu, journals-info@mit.edu}\@. Published one article at a time in \LaTeX\ source form on the Internet\@. Pagination varies from copy to copy\@. For more information and other articles see: \begin{itemize} \item \emph{http://mitpress.mit.edu/CJTCS/} \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/} \item \emph{ftp://mitpress.mit.edu/pub/CJTCS} \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs} \end{itemize} \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is abstracted or indexed in \emph{ Research Alert,\registered SciSearch, \registered Current Contents\registered/Engineering Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered} \par\noindent\copyright 1999 The Massachusetts Institute of Technology\@. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to ensure fair attribution to authors and the journal, and to prohibit use in a competing commercial product\@. See the journal's World Wide Web site for further details\@. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; \emph{journals-rights@mit.edu}\@.\pagebreak[2] \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is a peer-reviewed scholarly journal in theoretical computer science\@. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science\@. \par \begin{trivlist} \item[\emph{Editor-in-Chief:}] Janos Simon \item[\emph{Consulting Editors:}] Joseph Halpern, Eric Allender, Raimund Seidel \item[\emph{Editors:}] \begin{tabular}[t]{lll} Martin Abadi & Greg Frederickson & John Mitchell \\ Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\ Georg Gottlob & Gil Neiger & Tetsuo Asano \\ Vassos Hadzilacos & David Peleg & Laszl\'o Babai \\ Juris Hartmanis & Andrew Pitts & Eric Bach \\ Maurice Herlihy & James Royer & Stephen Brookes \\ Ted Herman & Alan Selman & Jin-Yi Cai \\ Stephen Homer & Nir Shavit & Anne Condon \\ Neil Immerman & Eva Tardos & Cynthia Dwork \\ Howard Karloff & Sam Toueg & David Eppstein \\ Philip Klein & Moshe Vardi & Ronald Fagin \\ Phokion Kolaitis & Stuart Kurtz & Jennifer Welch \\ Lance Fortnow & Stephen Mahaney & Pierre Wolper \\ Steven Fortune & Michael Merritt \end{tabular} \vspace{1ex} \item[\emph{Managing Editor:}] Michael J.\ O'Donnell \vspace{1ex} \item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu} \end{trivlist} \vfil\null \end{titlepage} \maketitle \pagenumbering{arabic} %% %% End Titlepage code %% \begin{abstract} We show that the permanent cannot be computed by uniform constant-depth threshold circuits of size $T(n)$ for any function $T$ such that for all $k$, $T^{(k)}(n) = o(2^n)$. More generally, we show that any problem that is hard for the complexity class C$_=$P requires circuits of this size (on the uniform constant-depth threshold circuit model). In particular, this lower bound applies to any problem that is hard for the complexity classes PP or \#P. This extends a recent result by Caussinus, McKenzie, Th\'{e}rien, and Vollmer \cite{cj99-07-21}, showing that there are problems in the counting hierarchy that require superpolynomial-size uniform TC$^0$ circuits. The proof in \cite{cj99-07-21} uses ``leaf languages'' as a tool in obtaining their separations. Their proof does not immediately yield larger lower bounds for the complexity of these problems, and it also does not yield a lower bound for any particular problem at any fixed level of the counting hierarchy. (It only shows that hard problems must exist at \emph{some} level of the counting hierarchy.) We also present related and somewhat weaker lower bounds, extending the theorem of \cite{cj99-07-21} showing that ACC$^0$ is properly contained in ModPH. \end{abstract} \section{Introduction} \subsection{Motivation and background} The central problem in complexity theory is the task of proving lower bounds on the complexity of specific problems. Circuit complexity, in particular, the study of constant-depth circuits, is one of the few areas where complexity theory has succeeded in actually providing lower bounds. Yet even in the study of constant-depth circuits, one quickly arrives at the limits of current lower-bound technology. It is known that constant-depth circuits of AND, OR, and NOT gates (so-called AC$^0$ circuits) require exponential size, even to compute the parity of $n$ input bits (see \cite{cj99-07-25,cj99-07-24}), and similar lower bounds are known for constant-depth circuits of AND, OR, NOT, and MOD$p$ gates where $p$ is prime (refer to \cite{cj99-07-11,cj99-07-23}). When MOD$m$ gates are allowed for composite $m$, however, almost nothing is known. It remains an open question if there is any problem in NTIME($2^{n^{O(1)}}$) that cannot be done with polynomial size and constant depth with AND and MOD6 gates. There is considerable reason to be interested in circuits with AND, OR, and MOD$m$ gates; circuits of this sort are called ACC$^0$ circuits (for ``alternating circuits with counters''; the superscript $0$ refers to the circuit depth of $O(\log^0 n)$). The lovely result of \cite{cj99-07-03} characterizing NC$^1$ (log-depth fan-in two circuits) in terms of constant-width branching programs relies heavily on algebraic techniques and shows that NC$^1$ corresponds to computation over \emph{nonsolvable} algebras. Barrington also defined the corresponding notion of computation over \emph{solvable} algebras, and it is shown in \cite{cj99-07-05} that this notion corresponds exactly to ACC$^0$ circuits. To restate these two points: \begin{enumerate} \item The results of \cite{cj99-07-03} establish intimate connections between circuit complexity and algebraic structure. \item In this algebraic setting, ACC$^0$ is the most important subclass of NC$^1$. \end{enumerate} Although, as mentioned above, it is unknown if small ACC$^0$ circuits suffice to compute all problems in NTIME$(2^{n^{O(1)}})$, lower bounds for \emph{uniform} ACC$^0$ circuits can be found in \cite{cj99-07-02}. The techniques of \cite{cj99-07-02} (see also \cite{cj99-07-27}) employ diagonalization, which is less useful in the nonuniform setting. Since our results, like those of \cite{cj99-07-21} and \cite{cj99-07-02}, concern uniform circuits, it is necessary to briefly discuss uniformity. A circuit family $\{C_n\}$ consists of a circuit for each input length $n$. If $C_n$ is ``sufficiently easy'' to construct from $n$, then the family $\{C_n\}$ is said to be \emph{uniform}. Different notions of ``sufficiently easy'' give rise to different notions of uniformity; the question of which is the ``right'' one to use when studying classes of circuits is not always clear. For the circuit classes considered here, convincing arguments are presented in \cite{cj99-07-04} % regarding the supremacy of a very restrictive notion of % uniformity called \emph{Dlogtime-uniformity}. making the case that a very restrictive notion of uniformity called \emph{Dlogtime-uniformity} is the correct notion to use. Briefly, a circuit family $\{C_n\}$ is Dlogtime-uniform if, given a tuple $(n,g,h)$, a deterministic Turing machine can, in time linear in the length of the string $(n,g,h)$, find whether gate $g$ is connected to gate $h$ in circuit $C_n$ % and also describe the nature of gates $g$ and $h$. and determine if $g$ and $h$ are AND gates, OR gates, input gates, etc. The length of the input $(n,g,h)$ is logarithmic in the size of the circuit $C_n$, which is why we call it Dlogtime-uniform. (Dlogtime-uniformity is essentially equivalent to what Ruzzo called $U_D$ uniformity in \cite{cj99-07-12}, although he considered only circuits of fan-in two, and not the unbounded fan-in circuits considered here and in \cite{cj99-07-04}.) Throughout the rest of this paper, all mention of uniform circuits refers to Dlogtime-uniform circuits. In addition, ACC$^0(S(n))$ denotes the class of languages with \emph{uniform} ACC$^0$ circuits of size $S(n)$. ACC$^0$ denotes ACC$^0(n^{O(1)})$. In contrast to our lack of lower bounds for nonuniform ACC$^0$ circuits for sets in NTIME($2^{n^{O(1)}}$), it was shown in \cite{cj99-07-02} that exponential size (i.e., size at least $2^{n^{\epsilon}}$) is required to compute the permanent (and other problems complete for \#P) on \emph{uniform} ACC$^0$ circuits. Thus there are sets in P$^{\mathrm \#P}$ that require exponential-sized uniform ACC$^0$ circuits. The complexity class PP is closely related to \#P (for instance, P$^{\mathrm \#P}$ = P$^{\mathrm PP}$). Recall that a set $A$ is in PP if there is a nondeterministic polynomial time machine $M$ with the property that $x \in A$ if and only if the number of accepting paths of $M$ on input $x$ is greater than the number of rejecting paths. PP contains both NP and coNP (see \cite{cj99-07-08}). Another related complexity class is C$_=$P; a set $A$ is in C$_=$P if there is a nondeterministic polynomial time machine $M$ with the property that $x \in A$ if and only if the number of accepting paths of $M$ on input $x$ is \emph{equal to} the number of rejecting paths. C$_=$P contains coNP but is not known to contain NP; PP is contained in NP$^{\mathrm C_=P}$ \cite{cj99-07-15}. One might expect that similar exponential lower bounds would hold for PP or C$_=$P as hold for \#P, but \cite{cj99-07-02} was able to show only that sets complete for these classes require more than sub-subexponential-size ACC$^0$ circuits, where the term ``sub-subexponential'' is made precise as follows. \begin{definition} A function $t$ is said to be \emph{sub-subexponential} if, for all $k$, \[t(t(n)^k) = 2^{n^{o(1)}}. \] \end{definition} In \cite{cj99-07-02} this term was defined slightly differently; in that paper, $t$ had to satisfy only the condition that $t(t(n)) = 2^{n^{o(1)}}$. Note that for all ``natural'' and interesting size bounds $t$, these conditions are equivalent. Observe that size bounds such as $2^{\log^k n}$ and $2^{(\log n)^{k\log\log n}}$ are sub-subexponential. Another class of constant-depth circuits that has attracted interest uses threshold (or MAJORITY) gates instead of counters. Let TC$^0(S(n))$ denote the class of sets accepted by uniform constant-depth threshold circuits of size $S(n)$; TC$^0$ denotes TC$^0(n^{O(1)})$. TC$^0$ captures the complexity of important natural computational problems such as sorting, counting, and integer multiplication. It is also a good complexity-theoretic model for the ``neural net'' model of computation (see \cite{cj99-07-26}). It is easy to observe that ACC$^0$ $\subseteq$ TC$^0$ (for example, see \cite{cj99-07-04}), and thus we have even fewer lower bounds for the threshold circuit model than for ACC$^0$ circuits. Furthermore, since TC$^0(s(n)) \subseteq$ DSPACE$(\log s(n))$ (for $s(n) \geq n$) and since (by an easy consequence of the space hierarchy theorem) for any PSPACE-complete set $A$ there is some $\epsilon > 0$ such that $A \not\in$ DSPACE$(n^\epsilon)$, it follows that PSPACE-complete sets require exponential-size uniform TC$^0$ circuits. Yet, there is still no smaller complexity class in PSPACE that is known to require exponential-size uniform TC$^0$ circuits. There are well-studied subclasses of PSPACE that correspond in a natural way to the complexity classes AC$^0$, ACC$^0$, and TC$^0$. The relationship between the polynomial hierarchy and AC$^0$ is well known and was established by \cite{cj99-07-07}. One way to present this correspondence is to observe that, when one considers alternating Turing machines that make only $O(1)$ alternations, a polynomial running time yields the polynomial hierarchy, while a logarithmic running time yields uniform AC$^0$. The analogous subclasses of PSPACE corresponding to ACC$^0$ and TC$^0$ are ModPH and the counting hierarchy, respectively. ModPH is in some sense a generalization of the polynomial hierarchy and of $\oplus$P (formal definitions appear in Section \ref{modsec}). The counting hierarchy (defined in \cite{cj99-07-17} and studied by several authors) consists of the union of the complexity classes PP, PP$^{\mathrm PP}$, PP$^{\mathrm PP^{\mathrm PP}}$, \ldots. (Note that this is equal to the union of the classes C$_=$P, C$_=$P$^{\mathrm C_=P}$, C$_=$P$^{\mathrm C_=P^{\mathrm C_=P}}$, \ldots.) In Section \ref{modsec}, we present models of computation (similar to alternating Turing machines) such that polynomial time on this model characterizes ModPH (or the counting hierarchy), while logarithmic time characterizes ACC$^0$ (or TC$^0$, respectively). \subsection{Statement of the main results} A recent paper by Caussinus, McKenzie, Th\'{e}rien, and Vollmer \cite{cj99-07-21} shows that ACC$^0$ is properly contained in ModPH, and TC$^0$ is properly contained in the counting hierarchy. The proof given by \cite{cj99-07-21} uses ``leaf languages'' as a tool and does not explicitly present a lower bound for any language in ModPH or in the counting hierarchy. The present work began as an attempt to discover if these techniques could be used to find an explicit lower bound. This attempt was only partially successful. For each given language $A$ in ModPH, it is \emph{still} an open question whether $A$ has polynomial-size uniform ACC$^0$ circuits. The proof in \cite{cj99-07-21} shows only that there \emph{exists} a set in ModPH that requires superpolynomial-size ACC$^0$ circuits; the present work gives a very simple direct proof of this same separation, but with the improvement that ``superpolynomial'' is replaced by ``sub-subexponential.'' In contrast, we \emph{are} able to give explicit lower bounds on the uniform threshold circuit size required for many problems in the counting hierarchy. Although we are able only to show that some set \emph{exists} in the counting hierarchy that requires more than sub-subexponential-size uniform threshold circuits, we \emph{can} obtain explicit lower bounds if we weaken the size bound only slightly. Recall that a function $t$ is sub-subexponential if $t^{(2)}(n) = 2^{n^{o(1)}}$, where $t^{(k)}$ denotes $t$ composed with itself $k$ times. We obtain a smaller class of functions if we impose the harsher restriction that for \emph{all} $k$, $t^{(k)}(n) = o(2^n)$, but there seem to be no natural functions of interest that satisfy the former condition but not the latter. In particular, functions $t$ such as $2^{\log^k n}$ and $2^{(\log n)^{k\log\log n}}$ satisfy the condition that for all $k$, $t^{(k)}(n) = o(2^n)$. The main result of this paper can now be stated. \newenvironment{maintheorem} {\begin{trivlist}\item[\hskip\labelsep{\textbf{Main theorem (Theorem \ref{mainthm})}}]\it} {\end{trivlist}} \begin{maintheorem} Let $A$ be hard for {\rm C$_=$P} under $\leq^{\mathrm TC^0}_{\mathrm T}$ reducibility, and let $t$ be a function such that for all $k, t^{(k)}(n) = o(2^n)$. Then $A \not\in TC^0(t(n))$. \end{maintheorem} The notion of $\leq^{\mathrm TC^0}_{\mathrm T}$ reducibility is defined as follows. Let $A$ and $B$ be subsets of $\{0,1\}^*$. Then $A \leq^{\mathrm TC^0}_{\mathrm T} B$ if there is a uniform family of polynomial-size constant-depth circuits with MAJORITY gates and oracle gates for $B$, accepting $A$. (This is a natural adaptation of the notion of AC$^0$ reducibility studied in \cite{cj99-07-18} and elsewhere.) In particular, all sets that are currently known to be complete for PP require threshold circuits of this size, because all such sets currently known are in fact complete under many-one reductions computable in uniform AC$^0$. \begin{corollary} The permanent cannot be computed by uniform constant-depth threshold circuits of size $t(n)$ if, for all $k, t^{(k)}(n) = o(2^n)$. \end{corollary} \begin{proof} It was shown in \cite{cj99-07-20} (see also comments in \cite{cj99-07-02}) that the set $\{(x,i,b) \mid \mbox{the}\ i\mbox{th bit of PERMANENT}(x)\ \mbox{is equal to}\ b\}$ is hard for C$_=$P under AC$^0$ reducibility (with only one query). Thus Theorem \ref{mainthm} applies. \end{proof} In contrast, some of the functions that are shown to be \#P-complete in \cite{cj99-07-16} are shown to be complete \emph{only\/} under \emph{polynomial-time Turing} reducibility; for example, we have not checked to see if the problem of counting the number of (possibly imperfect) matchings in a bipartite graph is hard for C$_=$P under $\leq^{\mathrm TC^0}_{\mathrm T}$ reducibility (although we suspect that this is the case), and until this is established, the lower bounds of this paper are not known to hold for this problem. Similarly, the functions that are shown by Toda in \cite{cj99-07-14} to be complete for FP$^{\mathrm \#P}$ are not immediately known to require large threshold circuits; it first needs to be established that they are hard for C$_=$P under TC$^0$ reductions. \section{Machine models} \label{modsec} We assume the reader is familiar with nondeterministic oracle Turing machines. Given natural number $m$ and oracle $A$, Mod$_m$P$^A$ is the class of languages $B$ such that, for some nondeterministic polynomial-time Turing machine $M$, $x$ is in $B$ if and only if the number of accepting computations of $M^A$ on input $x$ is a multiple of $m$. Then the class ModPH is defined to be the smallest class of languages containing P and with the property that if $A$ is in ModPH, then so are NP$^A$ and Mod$_m$P$^A$ for every natural $m$. ModPH has been studied by several authors (see, for example, \cite{cj99-07-09}). It is useful to have a model of computation characterizing ACC$^0$ and ModPH, in the same way that alternating Turing machines characterize both AC$^0$ and the polynomial hierarchy. The appropriate model of computation was defined in \cite{cj99-07-02} as a variant of alternating Turing machines. We refer the reader to \cite{cj99-07-02} for detailed definitions; for the purposes of this paper it suffices for the reader who is familiar with alternating Turing machines to consider the most natural way of augmenting the usual existential and universal states of an alternating Turing machine, by adding Mod$_m$ states. (Intuitively, a Mod$_m$ configuration $C$ of an alternating Turing machine is accepting if and only if $i$ is a multiple of $m$, where $i$ is the number of accepting configurations that are reachable from $C$ and are at the start of the next ``alternation level.'') Let a \emph{signature} $\sigma$ be a finite string from $\{\forall, \exists, {\mathrm Mod}_2, {\mathrm Mod}_3, {\mathrm Mod}_4,\ldots\}^*$. For any alternating Turing machine making $O(1)$ alternations, each path in the alternating tree of the machine on any input $x$ has a signature given by the sequence of types of states the machine enters. If $M$ is an alternating machine such that, on all inputs $x$, all paths have the same signature $\sigma$, then $M$ is said to be a $\sigma$ machine. For instance, the signature of a $\Sigma_2$ machine is $\exists\forall$, and the signature of a typical machine accepting a language in ${\mathrm NP^{\oplus P^{Mod_7 P}}}$ is $\exists {\mathrm Mod}_2 {\mathrm Mod}_7$. Let $\sigma$time$(t(n))$ denote the class of languages accepted by $\sigma$ machines running in time $t(n)$. The technical lemmas in \cite{cj99-07-02} essentially prove the following proposition. \begin{definition} Let us call a function $f$ \emph{constructible} if $f(n) = 2^{g(n)}$, where the binary representation of $g(n)$ can be computed from the binary representation of $n$ in time $O(g(n))$. \end{definition} \begin{proposition} Let $2^{t(n)}$ be a constructible function, $t(n) = \Omega(\log n)$. Then uniform {\rm ACC}$^0(2^{O(t(n))})$ = $\bigcup_{\sigma} \sigma$time$(O(t(n)))$. \end{proposition} It turns out to be useful to us to note that a ``tape reduction theorem'' holds for $\sigma$ machines. (In some ways, this can be viewed as a generalization of \cite{cj99-07-29}.) \begin{proposition} Let $\sigma$ be any nonempty signature. If a set is accepted in time $t(n)$ by a $\sigma$ machine with $k$ worktapes, then it is also accepted in time $O(t(n))$ by a $\sigma$ machine with two worktapes. \end{proposition} \begin{proof} Given a $k$-tape $\sigma$ machine, follow the construction in \cite{cj99-07-02} and build an ACC$^0$ circuit, such that $\sigma$ is the sequence of types of gates encountered in a root-to-leaf path. (Note that if the signature $\sigma$ is in $\{\forall,\exists\}^*$, then this is actually an AC$^0$ circuit.) In the construction given in \cite{cj99-07-02}, the deterministic linear-time machine that checks the uniformity condition needs $k$ tapes. Let us briefly explain: The gates of the circuit are labeled with configurations of the $\sigma$-machine at points in the computation when an alternation is made, and the labels also include a sequence of bits denoting the path in the alternation tree that leads from the first configuration to the second. The output gate of the circuit is labeled with the start configuration of the $\sigma$ machine. In order to determine what gates are connected, the ``uniformity machine'' needs only to simulate the $\sigma$-Turing machine along that path; if the $\sigma$-machine has $k$ tapes, then the uniformity machine has $k$ tapes, too. However, suppose we change the naming convention for the gates in the circuit in order to utilize the original tape-reduction proof for nondeterministic machines in \cite{cj99-07-06}. Then we can make do with a two-tape deterministic machine checking the uniformity condition. That is, let $M_1$ be the $k$-tape uniformity machine for the original circuit family. If the original circuit has gates $g$ and $h$, where there is an edge in the circuit from $h$ to $g$---corresponding to a computation path of the $\sigma$ machine from $g$ to $h$---then the new circuit has gates $(g,u)$ and $(h,uv)$, where $v$ is a string of length $t(n)$ recording the reading from each of the $k$ heads of the uniformity machine $M_1$ in the computation of length $t(n)$, which verifies that $h$ is connected to $g$. Since there are only $O(1)$ alternations of the $\sigma$-machine, and hence the circuit has depth $O(1)$, the label size is still $O(t(n))$ bits, and thus the circuit size is still $2^{O(t(n))}$. Now given a uniform $\sigma$-circuit family where the uniformity condition is checked by a two-tape machine, the construction in \cite{cj99-07-02} yields a two-tape $\sigma$-machine accepting the original language. \end{proof} Similarly, we find it very convenient to have a single model of computation that is sufficient for describing both TC$^0$ and the counting hierarchy. Such a model is described in \cite{cj99-07-10}. In the model, which is called a ``threshold Turing machine,'' TC$^0$ corresponds to $O(\log n)$ time and $O(1)$ uses of the threshold operation, and the counting hierarchy corresponds to polynomial time and $O(1)$ uses of the threshold operation. The characterization of the counting hierarchy in terms of threshold Turing machines is given in \cite{cj99-07-10}, but the corresponding characterization of TC$^0$ is \emph{not} presented there (since \cite{cj99-07-10} predates the uniformity considerations of \cite{cj99-07-04}). It does not seem to have been published anywhere else. Although \cite{cj99-07-04} \emph{does} give many equivalent characterizations of TC$^0$, the threshold Turing machine model is not mentioned in \cite{cj99-07-04}. Nonetheless, the proof of the following proposition is quite standard and follows along the lines of related results in \cite{cj99-07-10,cj99-07-04}. \begin{proposition}\label{mm1} % Let $t(n)$ be a % constructible function, $t(n) = \Omega(\log n)$. Then % uniform threshold circuit depth$(O(1))$, size$(2^{O(t(n))})$ = % threshold Turing machine time$(O(t(n)))$, thresholds$(O(1))$. Let $t(n)$ be a constructible function, $t(n) = \Omega(\log n)$. Then the following classes are equal: \begin{enumerate} \item Uniform threshold circuit depth$(O(1))$, size$(2^{O(t(n))})$ \item Threshold Turing machine time$(O(t(n)))$, thresholds$(O(1))$. \end{enumerate} \end{proposition} As is the case with the $\sigma$ machines considered above, the threshold Turing machines also enjoy a tape-reduction property, proved in essentially the same way. If a set is accepted in time $t(n)$ by a $k$-tape threshold Turing machine, it is accepted in time $O(t(n))$ by a two-tape threshold Turing machine. The lower bounds presented in this paper do not depend on this tape reduction, but the statement of Theorem \ref{diag} is simplified by taking advantage of the tape reduction. \section{Diagonalization} It is important to note that the techniques used to prove the nondeterministic time hierarchy (originally proved in \cite{cj99-07-13}; we use the very simple and general version proved by \v{Z}\'{a}k \cite{cj99-07-19}) can be used to prove analogous hierarchies for other computational models defined in terms of nondeterministic Turing machines (with a fixed bound on the number of worktapes). In particular, an essentially word-for-word translation of the proof in \cite{cj99-07-19} shows the following. \begin{theorem}\label{diag} Let $2^T$ be constructible. Then there is a set $B$ in $\sigma$time$(T(n))$ such that, for all $t$ with $t(n+1)=o(T(n))$, $B$ is not in $\sigma$time$(t(n))$. Also, there is a set $D$ in threshold Turing machine time$(O(T(n)))$,thresholds$(k)$ such that, for all $t$ with $t(n+1)=o(T(n))$, $D$ is not in threshold Turing machine time$(O(t(n)))$,thresholds$(k)$. \end{theorem} \begin{proof} For completeness, we present the main outline of the proof. Let $M_1, M_2,\ldots$ be an enumeration of two-tape $\sigma$-machines (threshold machines, respectively). Let $f$ be a rapidly growing function such that time $T(f(i,n,s))$ is enough time for a \emph{deterministic} machine to compute the function \[(i,n,s) \mapsto \left\{ \begin{array}{ll} 1 & \mbox{if } M_i\ \mbox{accepts}\ 1^n\ \mbox{in}\ \leq s\ \mbox{steps} \\ 0 & \mbox{otherwise. } \end{array} \right. \] Note that letting $f(i,n,s)$ be greater than $T^{-1}(2^{2^{i+n+s}})$ is sufficient; it is important in our setting to handle \emph{sublinear} functions $T$. Now divide $\Sigma^*$ into regions, so that in region $j=(i,y)$, we diagonalize against machine $M_i$, thus ensuring that each machine is considered infinitely often. The regions are defined by functions \emph{start}$(j)$ and \emph{end}$(j)$, defined as follows: \emph{start}(1) = 1, \emph{start}$(j+1)$ = \emph{end}$(j)$+1, where \emph{end}$(j)$ = $f$($i$, \emph{start}$(j)$, $T$( \emph{start}$(j)$)) (where $j = (i,y)$). The important point is that, on input $1^{end(j)}$, a deterministic machine can, in time $T$, determine whether $M_i$ accepts $1^{start(j)}$ in less than or equal to $T$( \emph{start}$(j)-1$) steps. By picking $f$ appropriately easy to invert, we can guarantee that, on input $1^n$, we can in time $T(n)$ determine which region $j$ contains $n$. Now it is easy to verify that the following routine can be computed in time $T(n)$ by a $\sigma$-machine (or a threshold machine, respectively). In the pseudocode below, $U$ is a ``universal'' $\sigma$-machine (or threshold machine) with four tapes, which is therefore able to simulate one step of machine $M_i$ in about $i^3$ steps. \begin{enumerate} \item On input $1^n$, determine which region $j$ contains $n$. Let $j = (i,y)$. \item If $n$ = \emph{end}$(j)$, then accept if and only if $M_i$ does \emph{not} accept $1^{start(j)}$ in $\leq T$( \emph{start}$(j)-1$) steps. \item Otherwise, accept if and only if $U$ accepts $(i,1^{n+1})$ in $\leq T(n)$ steps. (Here, it is important that we are talking about $T(n)$ steps of $U$, which may be only about $T(n)/i^3$ steps of $M_i$.) \end{enumerate} Let us call the set defined by the preceding pseudocode $A$. Clearly, $A$ is in $\sigma$time$(T(n))$. We now claim that is is not in $\sigma$time$(t(n))$. Assume otherwise, and let $M_i$ be the $\sigma$ machine accepting $A$ in time $t(n)$. Let $c$ be a constant such that $i^3t(n+1) < T(n)$ for all $n \geq c$. Let $y$ be a string of length greater than or equal to $c$, and consider stage $j = (i,y)$. Then for all $n$ such that \emph{start}$(j) \leq n <$ \emph{end}$(j)$, we have $1^n \in A$ if and only if $1^{n+1} \in A$. However, this contradicts the fact that $1^{start(j)} \in A$ if and only if $1^{end(j)} \not\in A$. \end{proof} \section{Nonconstructive lower bounds} Once the definitions are in hand, the proof is now quite straightforward. \begin{theorem} Let $t$ be a constructible sub-subexponential function. Then there exist sets $A$ in {\rm ModPH} requiring size greater than $t(n)$ to compute on uniform {\rm ACC}$^0$ circuits. \end{theorem} \begin{proof} Let $t$ be given. Let $C$ be a set complete for P under Dlogtime-uniform projections. A ``projection'' is a function computable by a circuit with no gates other than NOT gates. A projection is Dlogtime-uniform if the circuit satisfies the usual Dlogtime-uniformity conditions. For more background and motivation, see \cite{cj99-07-28}. For instance, the standard complete set \{$(i,x,0^j) : M_i$ accepts $x$ in time $j$\} is a good choice for $C$. The proof consists of two cases: \begin{itemize} \item $C$ requires size greater than $t(n)$ to compute on uniform ACC$^0$ circuits. In this case, of course there is nothing to prove. \item $C$ can be computed by uniform ACC$^0$ circuits of size $t(n)$. Since $t$ is constructible, let $g$ be the function such that $t(n) = 2^{g(n)}$. In this case, it must happen that there is some $\sigma$ such that ACC$^0$ is in $\sigma$time$(g(n^{O(1)}))$, because uniform circuits for any set reducible to $C$ can easily be constructed from the ACC$^0$ circuits for $C$. \end{itemize} Now standard translational techniques can be used to show that for any signature $\tau$, $\tau$time($g(n)$) is contained in $\sigma$time$(g(t(n)^{O(1)}))$. To see this, consider any language $A$ in $\tau$time($g(n)$). Let $A'$ = \{$x10^j : j+|x|+1 = t(|x|)$ and $x \in A$\}. Our constructibility assumptions on $t$ ensure that $A'$ is in ACC$^0$ and, hence, is in $\sigma$time$(g(n^l))$ for some $l$. Let $M$ be this $g(n^l)$-time-bounded $\sigma$ machine accepting $A'$. The $\sigma$ machine $M'$ that, on input $x$, simulates $M$ on input $x10^{t(|x|)-|x|-1}$ runs in time $g(t(n)^l)$. Since $t$ is sub-subexponential, $2^{n^{\epsilon}} > t(t(n)^l) = 2^{g(t(n)^l)}$ and thus $g(t(n)^l) = o(n)$. Thus it follows from Theorem \ref{diag} that there is a set $B$ in $\sigma$time$(n)$ (and hence in ModPH) such that, for all $l$, $B$ is not in $\sigma$time$(g(t(n)^l))$ Therefore, $B$ is not in $\tau$time$(g(n))$ and does not have uniform ACC$^0$ circuits of size $t(n)$. \end{proof} It is important to note that, because of the nonconstructive nature of the proof of this theorem, the proof offers no clue as to \emph{what} set in ModPH has large ACC$^0$ circuits. An essentially identical proof yields the following theorem. \begin{theorem}\label{subsubthm} Let $t$ be a constructible sub-subexponential function. Then there exist sets $A$ in the counting hierarchy requiring size greater than $t(n)$ to compute on uniform threshold circuits. \end{theorem} \section{Main result} \begin{theorem} \label{mainthm} Let $t$ be a constructible function such that for all $k$, $t^{(k)}(n) = o(2^{n})$. Let $A$ be any set that is hard for C$_=$P under $\leq^{\mathrm TC^0}_{\mathrm T}$ reductions. Then $A$ cannot be computed by uniform constant-depth threshold circuits of size $t(n)$. \end{theorem} \begin{proof} Assume otherwise. Then we can show that for every set $B$ in the counting hierarchy, there is some $k$ such that $B$ has uniform constant-depth threshold circuits of size $T(n) = t^{(k)}(n)$. But since $T(T(n)) = 2^{n^{o(1)}}$, this contradicts Theorem \ref{subsubthm}. For the purposes of this proof, define CH$_1$ to be C$_=$P, and for $i > 1$, define CH$_i$ to be C$_=$P$^{{\mathrm CH}_{i-1}}$. First note that, under the assumption, C$_=$P has circuits of size $$ t(n^{O(1)})n^{O(1)} = O(t(t(t(n)))). $$ The circuit consists of a polysize TC$^0$ reduction {from} the C$_=$P set to $A$, where the oracle gates are replaced by circuits for $A$. Here, we assume without loss of generality that $t(n) \geq n^{\log n}$. Otherwise, we can take $t'$ to be the maximum of $t(n)$ and $n^{\log n}$. Now assume that all sets in CH$_i$ have uniform constant-depth circuits of size $O(t^{(4i)}(n))$, and consider a set $A \in$ CH$_{i+1}$. Thus there is some nondeterministic machine $M$ and a set $D \in$ CH$_i$ such that $M^D$ has exactly as many accepting paths as rejecting paths on input $x$ if and only if $x \in A$. The set \{$(x,C)$ : $M$ has exactly as many accepting paths as rejecting paths on input $x$, when all oracle queries are answered according to the circuit $C$\} is in C$_=$P and, by the basis case, has circuits of size $t(t(t(|(x,C)|)))$. When we replace $C$ by the circuit for $A$ that exists by inductive hypotheses, we obtain a circuit of size less than or equal to $t^{(3)}(n + t^{(4i)}(n)) \leq t^{(4(i+1))}(n)$. \end{proof} We do not know how to prove an explicit lower bound for any problem in ModPH that would be analogous to Theorem \ref{mainthm}. It is easy to observe, by the same proof techniques, the existence of a set that is complete either for NP or for Mod$_p$P for some prime $p$ that requires large ACC$^0$ circuits. Thus, in order to find a set that is not in ACC$^0$, one need not consider anything beyond one of the ``bottom'' levels of ModPH. However, unlike the counting hierarchy, there are infinitely many such bottom levels in ModPH. \section{More separations} {From} the foregoing, we know that TC$^0$ is properly contained in C$_=$P (and hence is properly contained in PP). Note, however, that C$_=$P is not known (or expected) to have circuits of less than exponential size. It is natural to ask if exponential size is necessary in order to find a language that is not in TC$^0$. In this section we show that it is not necessary; smaller size is sufficient in order to define languages that are not in TC$^0$. (On the other hand, merely having superpolynomial size is \emph{not} known to be sufficient.) First we make a simple observation. \begin{proposition} For all $\epsilon > 0$, {\rm ACC}$^0$ is properly contained in \begin{center} $($DTIME$(n^{\epsilon}) \cup \bigcup_\sigma \sigma$time$(\log n \log^* n))$. \end{center} \end{proposition} \begin{proof} By standard padding methods, it is easy to construct a set $A \in$ DTIME$(n^\epsilon)$ that is complete for P under projections. This set $A$ is thus also hard for ACC$^0$ under projections. If $A$ is not in ACC$^0$, then this yields the desired conclusion. Otherwise, $A$ is in ACC$^0$ and is therefore in $\sigma$time$(O(\log n))$ for some $\sigma$. Since $\sigma$time$(O(\log n))$ is closed under projections, it follows that ACC$^0$ is equal to $\sigma$time$(O(\log n))$. By diagonalization, we obtain that ACC$^0$ is properly contained in $\sigma$time$(O(\log n \log^* n))$. \end{proof} An identical proof yields the following. \begin{proposition} For all $\epsilon > 0$, {\rm TC}$^0$ is properly contained in \begin{center} $($DTIME$(n^{\epsilon}) \cup {\mathrm TC}^0(n^{O(\log^* n)})$. \end{center} \end{proposition} (By essentially the same argument, we obtain that {\rm TC}$^0$ is properly contained in {\rm NC}$^1$ $\cup {\mathrm TC}^0(n^{O(\log^* n)})$.) We immediately get the following corollaries, which seem only marginally better than the results of \cite{cj99-07-21} showing proper inclusion in ModPH and the counting hierarchy. \begin{corollary} Let $\epsilon$ be greater than $0$. Then \begin{center} {\rm ACC}$^0$ is properly contained in {\rm ACC}$^0(2^{n^\epsilon})$.\\ {\rm TC}$^0$ is properly contained in {\rm TC}$^0(2^{n^\epsilon})$. \end{center} \end{corollary} But now we use the technique of \cite{cj99-07-01} to get a better separation. \begin{lemma} Let $S$ be a constructible function such that $S(n) \geq n$. If {\rm ACC}$^0$ = {\rm ACC}$^0(S(n))$, then {\rm ACC}$^0$ = {\rm ACC}$^0(S(S(n)))$. \end{lemma} \begin{proof} Let $A$ be any set in $\sigma$time$(O(\log S(S(n))))$. Since a constructible function $S(n)$ is of the form $2^{g(n)}$, this means that $A$ is in $\sigma$time$(O(g(S(n))))$. Let $A'$ be the padded version $\{x10^{S(|x|)-|x|-1} : x \in A\}$. Our assumption implies that $A'$ is in ACC$^0$ and, thus, is in $\sigma'$time$(O(\log n))$ for some $\sigma'$. This in turn implies that $A$ is in $\sigma'$time$(O(\log(S(n))))$ and, thus, by assumption, is in ACC$^0$. \end{proof} \begin{corollary} Let $T$ be a constructible function such that, for some $k$ and all large $n$, $T^{(k)}(n) > 2^n$, where $T^{(k)}$ is $T$ composed with itself $k$ times. Then \begin{center} {\rm ACC}$^0$ is properly contained in {\rm ACC}$^0(T(n))$. \end{center} \end{corollary} \begin{corollary} Let $T$ be a constructible function such that, for some $k$ and all large $n$, $T^{(k)}(n) > 2^n$. Then \begin{center} {\rm TC}$^0$ is properly contained in {\rm TC}$^0(T(n))$. \end{center} \end{corollary} \section{Conclusions and open problems} It is often harder to ask the right question than to answer that question. In \cite{cj99-07-02} we presented lower bounds on the uniform circuit complexity of certain problems in PSPACE, and we did not see any way to prove lower bounds on the ACC$^0$ circuit complexity of any given problem in ModPH. Given the inspiration of \cite{cj99-07-21}, it is easy to give a direct proof showing that there \emph{exist} sets in ModPH having large ACC$^0$ circuit complexity, without giving lower bounds on any specific set in ModPH. This same technique, when taken one step further, provides explicit lower bounds for many specific problems in the counting hierarchy, including the complete sets for C$_=$P, PP, and several functions complete for \#P. An obvious question is whether the sub-subexponential lower bounds given here and in \cite{cj99-07-02} can be improved to exponential lower bounds. The lower bounds presented here for C$_=$P, PP, and the permanent are incomparable with the bounds presented in \cite{cj99-07-02}; the bounds presented here are for more powerful circuits (threshold circuits as opposed to ACC$^0$ circuits), but the size bounds presented here are not as large as in \cite{cj99-07-02}. It seems unlikely that the bounds presented here are optimal; probably exponential size is required for all of these problems. Of course, an even more desirable step would be to prove directly that MAJORITY requires exponential size for ACC$^0$ circuits. The so-called natural proofs framework of \cite{cj99-07-22} indicates that many lower bound proofs may be quite difficult to obtain. However, since ACC$^0$ is a very limited class in many respects (and, in particular, it is not clear that one should expect pseudo\-random generators to be computable in ACC$^0$), it is not clear that lower bounds for ACC$^0$ should be hard to obtain. \section*{Acknowledgments} I thank the authors of \cite{cj99-07-21} for making their manuscript available to me. I thank Dieter van Melkebeek for helpful discussions and Ken Regan for his suggestions. \subsection*{Acknowledgment of support} The author was supported in part by NSF grants CCR-9509603 and CCR-9734918. \addcontentsline{toc}{section}{Bibliography} \bibliographystyle{alpha} \bibliography{cj99-07} \end{document}