\documentclass[11pt]{article} \usepackage{amsmath} % when using euler, use amsmath instead of amstex %\usepackage{amstex} \usepackage{amssymb,amsbsy} % for AMS TeX symbols \usepackage{pifont} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Sectioning % % sections: % \makeatletter \renewcommand{\section}{\@startsection {section}% {1}% {0mm}% {-2\baselineskip}% {\baselineskip}% {\normalfont\large\bf}} \renewcommand{\subsection}{\@startsection {subsection}% {1}% {0mm}% {-2\baselineskip}% {\baselineskip}% {\normalfont\normalsize\bf}} \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Theorem environments and the like % diverse layout changes \makeatletter \def\@begintheorem#1#2{\parskip0pt plus3pt\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \def\@opargbegintheorem#1#2#3{\parskip0pt plus3pt\it \trivlist \item[\hskip \labelsep{\bf #1\ #2\ #3.}]} \makeatother % Environments with Text in Roman % i.e.: Definitions \makeatletter \def\newdefinition#1{\@ifnextchar[{\@odefi{#1}}{\@ndefi{#1}}} \def\@ndefi#1#2{% \@ifnextchar[{\@xndefi{#1}{#2}}{\@yndefi{#1}{#2}}} \def\@xndefi#1#2[#3]{\expandafter\@ifdefinable\csname #1\endcsname {\@definecounter{#1}\@addtoreset{#1}{#3}% \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand \csname the#3\endcsname \@deficountersep \@deficounter{#1}}% \global\@namedef{#1}{\@defi{#1}{#2}}\global\@namedef{end#1}{\@enddefi}}} \def\@yndefi#1#2{\expandafter\@ifdefinable\csname #1\endcsname {\@definecounter{#1}% \expandafter\xdef\csname the#1\endcsname{\@deficounter{#1}}% \global\@namedef{#1}{\@defi{#1}{#2}}\global\@namedef{end#1}{\@enddefi}}} \def\@odefi#1[#2]#3{\expandafter\@ifdefinable\csname #1\endcsname {\global\@namedef{the#1}{\@nameuse{the#2}}% \global\@namedef{#1}{\@defi{#2}{#3}}% \global\@namedef{end#1}{\@enddefi}}} \def\@defi#1#2{\refstepcounter {#1}\@ifnextchar[{\@ydefi{#1}{#2}}{\@xdefi{#1}{#2}}} \def\@xdefi#1#2{\@begindefi{#2}{\csname the#1\endcsname}\ignorespaces} \def\@ydefi#1#2[#3]{\@opargbegindefi{#2}{\csname the#1\endcsname}{#3}\ignorespaces} \def\@deficounter#1{\noexpand\arabic{#1}} \def\@deficountersep{.} %deleted September 2, 1986 MDK %\def\@makethmnumber#1#2{\bf #1 #2:} \def\@begindefi#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]\rm} \def\@opargbegindefi#1#2#3{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2\ #3.}]\rm} \def\@enddefi{\endtrivlist} \makeatother % % Environment-Vereinbarungen: \newtheorem{thm}{Theorem}[section] \newtheorem{coro}[thm]{Corollary} \newtheorem{lemma}[thm]{Lemma} \newtheorem{propo}[thm]{Proposition} \newtheorem{rem}[thm]{Remark} \newtheorem{question}{Open Question} \newdefinition{defi}[thm]{Definition} \newdefinition{example}[thm]{Example} \newdefinition{problem}[thm]{Problem} \newdefinition{remark}[thm]{Remark} % proof environment \newcommand\qedsymbol{\ding{113}} \def\endproof{{\unskip\nobreak\hfil\penalty50 \hskip1em\hbox{}\nobreak\qedsymbol \parfillskip=0pt\par\endtrivlist\addpenalty{-100}}} \def\proof{\trivlist \penum=1%penum: siehe unten! \item[\hskip \labelsep{\it Proof.}]} \def\endoutline{{\unskip\nobreak\hfil\penalty50 \hskip1em\hbox{}\nobreak\qedsymbol \parfillskip=0pt\par\endtrivlist\addpenalty{-100}}} \def\outline{\trivlist \penum=1%penum: siehe unten! \item[\hskip \labelsep{\it Proof sketch.}]} % eigenes enumerate fuer Beweise, um Platz zu sparen ... \newcount\penum \def\pitem{\ifnum\penum>1\par\fi\the\penum. \advance\penum by1} % numerierte Gleichungen, Bemerkungen, etc; % nur mit Nummer, ohne "Satz", "Korollar", ... \newenvironment{eqn} {\trivlist\refstepcounter{thm}\item[\hskip \labelsep{\bf \thethm.}]} {\endtrivlist} \newcounter{noheadsectionctr}[section] \def\noheadsection{\addtocounter{noheadsectionctr}{1} \par\noindent{\bf\arabic{section}.\arabic{noheadsectionctr}. }} \newcommand\todo[1]{\par{\sl #1}} \newcommand\marg[1]{\marginpar{\raggedright\footnotesize\sl #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % several hundred mathematical symbols \newcommand\EXPSPACE{{\rm EXPSPACE}} \newcommand\NEXPTIME{{\rm NEXPTIME}} \newcommand\EXPTIME{{\rm EXPTIME}} \newcommand\MIP{{\rm MIP}} \newcommand\PH{{\rm PH}} \newcommand\CH{{\rm CH}} \newcommand\PP{{\rm PP}} \newcommand\BPP{{\rm BPP}} \newcommand\RP{{\rm RP}} \renewcommand\P{{\rm P}} \newcommand\FP{{\rm FP}} \newcommand\NP{{\rm NP}} \newcommand\BH{{\rm BH}} \newcommand\UP{{\rm UP}} \newcommand\AM{{\rm AM}} \newcommand\PSPACE{{\rm PSPACE}} \newcommand\IP{{\rm IP}} \newcommand\IPP{{\rm IPP}} \newcommand\PCP{{\rm PCP}} \newcommand\Sigp[1]{\Sigma^{\rm p}_{#1}} \newcommand\Pip[1]{\Pi^{\rm p}_{#1}} \newcommand\Deltap[1]{\Delta^{\rm p}_{#1}} \newcommand\Thetap[1]{\Theta^{\rm p}_{#1}} \newcommand\Sigpo[2]{\Sigma^{{\rm p},#2}_{#1}} \renewcommand\L{{\rm L}} \newcommand\LOGSPACE{{\rm LOGSPACE}} \newcommand\NL{{\rm NL}} \newcommand\SymL{{\rm SymL}} \newcommand\numP{{\rm\#P}} \renewcommand\.{\mathop{\cdot}} \newcommand\co{{{\rm co}}} \newcommand\ex{\exists} \newcommand\fall{\forall} \renewcommand\c{\mathord{\rm C}} \newcommand\ceq{\c_=} \newcommand\pari{\mathord{\oplus}} \newcommand\num{\mathord{\rm\#}} \newcommand\Mod{\mathord{\rm Mod}} \newcommand\MidbitP{{\rm MidbitP}} \newcommand\MODPH{\text{\rm MOD-PH}} \newcommand\NC{{\rm NC}} \newcommand\AC{{\rm AC}} \newcommand\SAC{{\rm SAC}} \newcommand\NCe{{\rm NC}^1} \newcommand\ACn{{\rm AC}^0} \newcommand\ACCn{{\rm ACC}^0} \newcommand\TCn{{\rm TC}^0} \newcommand\BPNCe{{\rm BPNC}^1} \newcommand\qNC{{\rm qNC}} \newcommand\qNCe{{\rm qNC}^1} \newcommand\qTCn{{\rm qTC}^0} \newcommand\qACn{{\rm qAC}^0} \newcommand\qACCn{{\rm qACC}^0} \newcommand\DLOGTIME{{\rm DLOGTIME}} \newcommand\NLOGTIME{{\rm NLOGTIME}} \newcommand\FDLOGTIME{{\rm FDLOGTIME}} \newcommand\LOGCFL{{\rm LOGCFL}} \newcommand\POLYLOGTIME{{\rm POLYLOGTIME}} \newcommand\FPOLYLOGTIME{{\rm FPOLYLOGTIME}} \newcommand\POLYLOGSPACE{{\rm POLYLOGSPACE}} \newcommand\PLT{\POLYLOGTIME} \newcommand\PLS{\POLYLOGSPACE} \newcommand\CC{{\mathcalli{C}}} \newcommand\CD{{\mathcalli{D}}} \newcommand\F{{\mathcalli{F}}} \newcommand\K{{\mathcalli{K}}} \newcommand\M{{\mathcalli{M}}} \renewcommand\O{{\mathcalli{O}}} %\newcommand\N{{\rm I\!N}} % for Non-AMS \newcommand\N{{\mathbb{N}}} % for AMS \newcommand\Z{{\mathbb{Z}}} % for AMS \newcommand\set[2]{\bigl\{\,#1\bigm| #2\,\bigr\}} \newcommand\seq{\subseteq} \newcommand\qes{\supseteq} %\newcommand\implies{\Rightarrow} \newcommand\eqdef{=_{\rm def}} \newcommand\LeafP{{\rm Leaf}^\P} \newcommand\BLeafP{{\rm BalancedLeaf}^\P} \newcommand\leafM{{\rm leafstring}^{M}} \newcommand\leqplt{\leq^{{\it plt}}_m} \newcommand\REC{{\rm REC}} \newcommand\C{{\mathcalli{C}}} \newcommand\RAND{{{\rm RAND}}} \newcommand\GapP{{{\rm GapP}}} \newcommand\Gd{{\mbox{\rm G}_\delta}} \newcommand\Fs{{\mbox{\rm F}_\sigma}} \newcommand\Sige[1]{\Sigma^{\rm exp}_{#1}} \newcommand\Pie[1]{\Pi^{\rm exp}_{#1}} \newcommand\exz{\ex^2} \newcommand\fallz{\fall^2} \newcommand\PQH{{\rm PQH}} \newcommand\PQUERY{{\rm PQUERY}} \newcommand\NPb{{\rm NP_B}} \newcommand\mred{\leq^p_m} \newcommand\ttred{\leq^p_{{tt}}} \newcommand\bttred{\leq^p_{{btt}}} %\newcommand{\leqo}{\mathord{\leq}} \newcommand\leqo{{\mathcalli{R}}} \newcommand\leqcd{\leq_{{\rm cd}}} \newcommand\eqcd{\equiv_{{\rm cd}}} %\newcommand\Mu[1]{\text{Prob}[#1]} \newcommand\Mu[1]{\mu\left[#1\right]} \newcommand\MuA[1]{\mu_A\bigl[#1\bigr]} \newcommand\quark{\kern.5em} \newcommand\CSL{{\rm CSL}} \newcommand\CFL{{\rm CFL}} \newcommand\REG{{\rm REG}} \newcommand\RE{{\rm r.e.}} \newcommand\poly{n^{O(1)}} \newcommand\polylog{\log^{O(1)}n} \newcommand\Poly{/{\rm Poly}} \newcommand\pol{{\rm pol}} \newcommand\const{{\rm const}} \newcommand\ntisp{\text{\rm NTIME-SPACE}} \newcommand\dtisp{\text{\rm DTIME-SPACE}} \newcommand\dtime{\text{\rm DTIME}} \newcommand\ntime{\text{\rm NTIME}} \newcommand\dspace{\text{\rm DSPACE}} \newcommand\nspace{\text{\rm NSPACE}} \newcommand\atimespace{\text{\rm ATIME-SPACE}} \newcommand\size{\text{\rm SIZE}} \newcommand\depth{\text{\rm DEPTH}} \newcommand\side{\text{\rm SIZE-DEPTH}} \newcommand\uside{\text{\rm UnbSIZE-DEPTH}} \newcommand\SC{{\rm SC}} \newcommand\NSC{{\rm NSC}} \newcommand\mathcalli[1]{\mathcal{#1}} % for AMS-TeX %\newcommand\mathcalli[1]{{\cal #1}} % for non-AMS-TeX %\newcommand\text[1]{\mbox{#1}} % for non-AMS-TeX %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %local operators % \newcommand\exn{\exists^0} \newcommand\falln{\forall^0} \newcommand\exe{\exists^1} \newcommand\falle{\forall^1} %\newcommand\exz{\exists^2} %\newcommand\fallz{\forall^2} \newcommand\exs{\exists^\sigma} \newcommand\falls{\forall^\sigma} \newcommand\ext{\exists^\tau} \newcommand\fallt{\forall^\tau} \newcommand\bpn{\text{\rm BP}^0} \newcommand\bpe{\text{\rm BP}^1} \newcommand\bpz{\text{\rm BP}^2} \newcommand\bP{{(B)\P}} \newcommand\bbP{{(B')\P}} \newcommand\rel{^{(\cdot)}} \newcommand\almost{\mbox{\rm ALMOST-}} \newcommand\bph{{\mbox{\rm BP}^h}} \newcommand\bpp{{\mbox{\rm BP}^{\rm p}}} %\newcommand\bpe{{\mbox{\rm BP}^{\rm exp}}} %\newcommand\bpz{{\mbox{\rm BP}^2}} \newcommand\bpd{{\widehat{\mbox{\rm BP}}^2}} \newcommand\bpt{{\widetilde{\mbox{\rm BP}}^2}} \newcommand\cp{\c^{\rm p}} \newcommand\exlog{\exists^{\log}} \renewcommand\exp{\exists^{\text{\rm p}}} \newcommand\exexp{\exists^{\text{\rm exp}}} \newcommand\falllog{\forall^{\log}} \newcommand\fallp{\forall^{\text{\rm p}}} \newcommand\fallexp{\forall^{\text{\rm exp}}} \newcommand\bplog{\text{\rm BP}^{\log}} %\newcommand\bpp{\text{\rm BP}^{\text{\rm p}}} \newcommand\bpexp{\text{\rm BP}^{\text{\rm exp}}} \newcommand\rlog{\text{\rm R}^{\log}} \newcommand\rp{\text{\rm R}^{\text{\rm p}}} \newcommand\rexp{\text{\rm R}^{\text{\rm exp}}} \newcommand\corlog{\overline{\text{\rm R}}^{\log}} \newcommand\corp{\overline{\text{\rm R}}^{\text{\rm p}}} \newcommand\corexp{\overline{\text{\rm R}}^{\text{\rm exp}}} \newcommand\leqms{\leq^{\text{\rm p,s}}_m} \newcommand\emptystring{\epsilon} \renewcommand\vec[1]{\overrightarrow{#1}} %\setlength{\textheight}{8.875in} %\setlength{\textwidth}{6.875in} %\setlength{\columnsep}{0.3125in} %\setlength{\topmargin}{0in} %\setlength{\headheight}{0in} %\setlength{\headsep}{0in} %\setlength{\parindent}{1pc} %\setlength{\oddsidemargin}{-.304in} %\setlength{\evensidemargin}{-.304in} % \begin{document} \date{} \title{\Large\bf Characterizing Small Depth and Small Space Classes\\ by Operators of Higher Types} \author{Manindra Agrawal\thanks{Part of this research was done while visiting the University of Ulm under an Alexander von Humboldt Fellowship.}\\ Dept. of Computer Science\\ Indian Institute of Technology\\ Kanpur, India\\ {\tt e-mail: manindra@iitk.ac.in}\\ \ \\ Eric Allender\thanks{Supported in part by NSF grant CCR-9734918.}\\ Department of Computer Science, Rutgers University\\ Piscataway, NJ 08855, USA\\ {\tt e-mail: allender@cs.rutgers.edu}\\ \ \\ Samir Datta\thanks{Supported in part by NSF grant CCR-9734918.}\\ Department of Computer Science, Rutgers University\\ Piscataway, NJ 08855, USA\\ {\tt e-mail: sdatta@paul.rutgers.edu}\\ \ \\ Heribert Vollmer\\ Lehrstuhl f\"{u}r Theoretische Informatik, Universit\"{a}t W\"{u}rzburg \\ Am Hubland, D-97074 W\"{u}rzburg, Germany\\ {\tt e-mail: vollmer@informatik.uni-wuerzburg.de}\\ \ \\ Klaus W. Wagner\\ Lehrstuhl f\"{u}r Theoretische Informatik, Universit\"{a}t W\"{u}rzburg \\ Am Hubland, D-97074 W\"{u}rzburg, Germany\\ {\tt e-mail: wagner@informatik.uni-wuerzburg.de}\\ } \maketitle \begin{abstract} Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators quantifying over oracles. We obtain new characterizations of $\NCe$, $\L$, $\NL$, $\NP$, and $\NSC$ (the nondeterministic version of SC). In some cases, we prove that our simulations are optimal (for instance, in bounding the number of queries to the oracle). \end{abstract} \section{Introduction} Interactive proofs motivate complexity theorists to study new modes of computation. These modes have been studied to great effect in the setting of polynomial time (e.g.~\cite{sha92, LundFKN92, bafolu91}) %and small space-bounded classes (e.g.~\cite{coli89,FortnowL1993, %Is there any reason to cite BOTH versions of [Condon, Lipton]? EWA and small space-bounded classes (e.g.~\cite{FortnowL1993, CondonL95}). Is it possible to study interactive proofs in the context of even smaller complexity classes? Would such a study be useful or interesting? It has often proved very useful to study modes of computation on very small complexity classes, although it has not always been clear at first, just how these modes should be modeled. For instance, the definition of alternating Turing machine given in \cite{chkost81} does not allow an interesting notion of sublinear time complexity, whereas augmenting this model with random access to the input provides a useful model for studying circuit complexity classes such as $\NCe$ and $\ACn$ \cite{ruz81, sip83b}. How can one define a useful notion of interactive proof system for deterministic log time? In attempting to answer this and related questions, we take as our starting point the work of Baier and Wagner \cite{bawa98}, where it was shown that (single-prover and multi-prover) interactive proof systems can be modeled by quantifying over oracles applied to $\P$. This framework is defined quite elegantly in terms of operators acting on complexity classes, generalizing the framework initially presented by Sch\"{o}ning \cite{sch89}. We present the formal definitions below in Section \ref{opsec}. After we present our definitions, we quickly review in Section \ref{knownsec} the main results that were known previously, regarding characterizations of complexity classes in terms of operators applied to $\P$. The most important results regarding interactive proofs are stated there, as well as some additional characterizations due to Baier and Wagner. Then, in Section \ref{scaleNP}, we present the notion of ``scaling up'' and ``scaling down'' characterizations in this framework, and we present some instances where ``scaling down'' does hold, as well as some instances where ``scaling down'' does not hold, and we discuss some of the subtleties involved. We are able to successfully give scaled-down versions of the known characterizations involving nondeterministic time-bounded complexity classes, and the characterizations we give are essentially optimal. In this way, we obtain new characterizations of $\NP$ and $\NL$. Next, in Section \ref{scalepspace}, we consider how to ``scale down'' the known characterizations of space-bounded classes. In this way, we obtain new characterizations of $\NCe$ and $\NSC$, the nondeterministic counterpart of Steve's class $\SC$, i.e., $\NSC=\ntisp(\poly,\polylog)$. However, a number of open questions remain, regarding whether it is possible to obtain true ``scaled down'' versions of the characterization of $\PSPACE$ in terms of interactive proofs, as given in \cite{sha92}. \section{Definitions} \label{definitions} \subsection{Oracle Operators}\label{opsec} Let us start by formally defining the operators we will use in this paper. They are operators acting on oracles, and since later we are going to apply sequences of oracle quantifiers to some base class, we will need oracle machines with more than one oracle tape. \begin{defi}\label{relclass} A relativized class $\K$ of type $\sigma_1\cdots\sigma_k$ is given by a recursive enumeration $M_0,M_1,M_2,\dots$ of oracle machines with $k$ oracle tapes each where $\sigma_j\in\{0,1,2\}$ is the type of $M_i$'s $j$th oracle ($i\geq 0$, $1\leq j\leq k$). Here, an oracle of type 2 is a usual oracle with no restriction. An oracle of type 1 is an oracle where after every query the oracle query tape is not erased (hence every query is an extension of the previous query). An oracle of type 0 is simply a word. %Unless otherwise specified we assume %that the length of such a word is bounded by a polynomial in the input length. Access to this word is by using the oracle tape as an index tape to address bits at specified positions. Now $L(M_i)$ consists of exactly those tuples $(x,X_1,\dots,X_k)$ where $M$ halts accepting on the ``actual'' input $x$ with oracles $X_1,\dots,X_k$ where $X_i$ is of type $\sigma_i$. \end{defi} For sake of clarity we explicitly remark that resource bounds are measured in the length of the actual input $x$. \emph{In the case of space bounds, all oracle/index tapes are subject to the space restriction.} We ask the reader to note that we are following \cite{bawa98,bawa98b} in using the numbers $0,1,2$ to refer to different types of operators, because it offers notational convenience in this setting. This numbering is unrelated to the convention in type theory, in which atoms are referred to as type 0 objects, strings as type 1 objects, and oracles as type 2 objects, etc. %This is just an equivalent re-wording of what Heribert wrote. Okay? EWA Now we define the following operators \cite{bawa98}: \begin{defi}\label{defiopa} Let $\K$ be a relativized class of type $\sigma_1\cdots\sigma_k\sigma$. Then we define the following classes of type $\sigma_1\cdots\sigma_{k}$: For $\sigma=0$ and $h\colon\N\rightarrow\N$, we have $L\in\exists^h\.\K$ iff there is a $B\in\K$ such that $$ (x,X_1,\dots,X_k)\in L \iff \bigl(\exists y, |y|=h(|x|)\bigr) (x,X_1,\dots,X_k,y)\in B, $$ and $L\in\fall^h\.\K$ iff there is a $B\in\K$ such that $$ (x,X_1,\dots,X_k)\in L \iff \bigl(\forall y, |y|=h(|x|)\bigr) (x,X_1,\dots,X_k,y)\in B. $$ We use the superscript $\log$ to denote the union of all classes obtained by choosing $h\in O(\log n)$, p to denote the union of all classes obtained by choosing $h\in n^{O(1)}$, and exp to denote the union of all classes obtained by choosing $h\in 2^{n^{O(1)}}$. For $\sigma=1$ or $\sigma=2$, $L\in\exs\.\K$ iff there is a $B\in\K$ such that $$(x,X_1,\dots,X_k)\in L \iff (\exists Y)(x,X_1,\dots,X_k,Y)\in B,$$ and $L\in\falls\.\K$ iff there is a $B\in\K$ such that $$(x,X_1,\dots,X_k)\in L \iff (\forall Y)(x,X_1,\dots,X_k,Y)\in B.$$ \end{defi} Book, Vollmer, and Wagner in \cite{bovowa98} examined the bounded-error probabilistic operator of type 2. We repeat their definition together with the definitions of the corresponding type 0 operator (see e.g.~\cite{sch89}). We also consider a one-sided error operator in the case of type 0. \begin{defi} Let $\K$ be a relativized class of type $\sigma_1\cdots\sigma_k2$. Then the class $\bpz\.\K$ is of type $\sigma_1\cdots\sigma_k$, and $L\in\bpz\.\K$ iff there exists a set $B\in\K$ such that %for all inputs $(x,X_1,\dots,X_k)$, $$\MuA{(x,X_1,\dots,X_k)\in L \leftrightarrow (x,X_1,\dots,X_k,A)\in B}\geq {\textstyle\frac{2}{3}}.$$ The measure $\mu\colon2^{\{0,1\}^\omega}\rightarrow[0,1]$ is the product measure based on $\mu_0\colon2^{\{0,1\}}\rightarrow[0,1]$, where $\mu_0(\{0\})=\mu_0(\{1\})=\frac{1}{2}$. Here we identify as usual languages over $\{0,1\}$ as infinitely long sequences from $\{0,1\}^\omega$. \end{defi} \begin{defi} Let $h\colon\N\rightarrow\N$. Let $\K$ be a relativized class of type $\sigma_1\cdots\sigma_k0$. Then we say that \begin{enumerate} \item $L\in\bph\K$ iff there exists a $B\in\K$ such that $$ \text{prob}_{|y| = h(|x|)} \bigl[(x,X_1,\dots,X_k) \in L \leftrightarrow (x,X_1,\dots,X_k,y)\in B\bigr] \geq {\textstyle\frac{2}{3}}. $$ \item $L\in{\text{\rm R}}^h\K$ iff there is a $B\in\K$ such that $$\begin{array}{l} (x,X_1,\dots,X_k)\in L \rightarrow\text{prob}_{|y| = h(|x|)}\bigl[(x,X_1,\dots,X_k,y)\in B\bigr] \leq \frac{1}{2}, \\ (x,X_1,\dots,X_k)\not\in L \rightarrow\text{prob}_{|y| = h(|x|)}\bigl[(x,X_1,\dots,X_k,y)\in B\bigr] = 1. \end{array}$$ \item $L\in\overline{\text{\rm R}}^h\K$ iff there is a $B\in\K$ such that $$\begin{array}{l} (x,X_1,\dots,X_k)\in L \rightarrow\text{prob}_{|y| = h(|x|)}\bigl[(x,X_1,\dots,X_k,y)\in B\bigr] = 1, \\ (x,X_1,\dots,X_k)\not\in L \rightarrow\text{prob}_{|y| = h(|x|)}\bigl[(x,X_1,\dots,X_k,y)\in B\bigr] \leq \frac{1}{2}. \end{array}$$ \end{enumerate} \end{defi} In the following we will apply sequences of operators to base classes %(mostly $\P$) such that the resulting class is of type $\epsilon$ (without any oracle). That is, in the terminology of Definition~\ref{relclass} we have $k=0$ and we deal with a usual class of languages of simple words, not of tuples consisting of words and sets. The type of the base class will always be implicitly given {from} the context. If we write e.g.~$Q_1^{\sigma_1}\cdots Q_k^{\sigma_k}\.\P$, then $\P$ is a class of languages of $k+1$ tuples $(x,X_1,\dots,X_k)$ where for $1\leq j\leq k$, $X_j$ is of type $\sigma_j$ if $\sigma_j\in\{1,2\}$ and $X_j$ is of type 0 if $\sigma_j\in\{\text{\rm exp},\text{\rm p},\log\}$. \subsection{Restricting the Number of Queries} Let us now consider restrictions to the number of oracle queries or the number of spot checks on a random access input tape. \begin{defi} Let $k\geq0$, let $\sigma_1,\sigma_2,\dots,\sigma_k\in \{1,2,\text{\rm exp},\text{\rm p},\log\}$, and let $r_1,r_2,\dots,r_k\colon\N\rightarrow\N$. Let $$L\in Q_1^{\sigma_1}[r_1]Q_2^{\sigma_2}[r_2]\cdots Q_k^{\sigma_k}[r_k]\.\K$$ iff $L\in Q_1^{\sigma_1}Q_2^{\sigma_2}\cdots Q_k^{\sigma_k}\.\K$ via a $\K$ machine $M$ which on input $(x,X_1,\dots,X_k)$ makes at most $r_i(|x|)$ queries to the $i$-th oracle or random access input tape (for $1\leq i\leq k$). We omit $[r_i]$ if it does not constitute a real restriction (for example if it is greater than the runtime of the underlying machine). \end{defi} \subsection{Small Space and Small Depth Classes} In the rest of this paper, we will use the above defined operators to characterize complexity classes defined by small depth of Boolean circuits or small space on Turing machines. We assume the reader is familiar with the classes from the inclusion chain $$\NCe\seq\L\seq\NL\seq\NC^2\seq\cdots\seq\NC\seq\P\cap\PLS,$$ see, e.g., \cite{vol99}. We also make reference to the classes $$\begin{array}{r@{\ \eqdef\ }l} \SC^k & \dtisp(\poly,\log^kn) \qquad\text{ and}\\ \NSC^k & \ntisp(\poly,\log^kn). \end{array} $$ Steve's class $\SC$ \cite{coo79} is the union of all $\SC^k$, and $\NSC$, the nondeterministic analogue of Steve's class, is the union of all $\NSC^k$. Relating these to the above classes, only $\SC^{k}\seq\NSC^{k}\seq\PLS$ and $\NCe\seq\L=\SC^1\seq\SC^2$ is known. It is conjectured that $\NC$ and $\SC$ are incomparable; see \cite{ruz81}. \section{Known Results}\label{knownsec} The following relation between type 2 oracle operators and word operators is known: If $\K$ is a class defined by nondeterministic polynomial time machines (technically, $\K$ is {\em leaf language definable}, i.e, $\K=\LeafP(B)$ for some set $B$ \cite{helascvowa93,jemcth96}), then $Q^2\.\K=Q^{\text{\rm exp}}\.\K$, where $Q$ can be any one of the above operators \cite{bovowa98}. We remark that a connection between the $\bpz$ operator and ALMOST-classes has been established in \cite{mewa95,bovowa98}, see also \cite{vowa97}. There it was shown that for a great number of classes $\K$, the identities $$\bpz\.\K=\bpexp\.\K=\almost\K$$ hold, where $\almost\K$ is the set of all languages $L$ that ``$\K$-reduce'' to almost every language, precisely: the measure of the set of all $A$ such that $L\in\K^A$ is one. However the main motivation for studying the above operator formalism stems from the fact that many results in the area of interactive protocols and probabilistically checkable proofs can be formulated conveniently in terms of the operators defined in Section \ref{definitions}. Thus, when seeking an appropriate generalization to smaller complexity classes, the operator formalism is convenient. Fortnow, Rompel, and Sipser in 1988 (see \cite{FortnowRS1994}) characterized the power of multi-prover interactive proofs by an existential operator ranging over oracles. Baier and Wagner in 1996 obtained the corresponding result for single-prover interactive proofs. \begin{thm}\label{ipmip}\leavevmode \begin{enumerate} \item $\NEXPTIME=\MIP = \exz\.\bpp\.\P = \exz\.\corp\.\P$ {\rm\cite{FortnowRS1994, bafolu91}}. \item $\PSPACE=\IP=\exe\.\bpp\.\P = \exe\.\corp\.\P$ {\rm\cite{bawa98, sha92}}. \end{enumerate} \end{thm} Because the first equality in both statements is {\em not\/} relativizable, this yields non-relativizable operator characterizations of the classes $\PSPACE$ and $\NEXPTIME$. In contrast to this, the following characterizations (obtained in \cite{bawa98b}) are relativizable. \begin{thm}\label{nexppsp}\leavevmode \begin{enumerate} \item $\NEXPTIME=\exz\.\fallp\.\P=\exz[3]\.\fallp\.\P$. \item $\PSPACE=\exe\.\fallp\.\P=\exe[2]\.\fallp\.\P$. \end{enumerate} \end{thm} Because we will use the technique again later on to show our results, we briefly review the proof of the left to right inclusions. \begin{outline} \pitem The proof builds on a translation of the completeness of 3SAT for $\NP$ under $\DLOGTIME$-reductions into the exponential time context, cf.~Theorem~\ref{NP3sat} in the next section. \pitem (Cf.~\cite[Theorem 9.2]{bawa98}.) The following (relativizable) characterization of $\PSPACE$ is known \cite{cafu91,helascvowa93}: A language $L$ is in $\PSPACE$ iff there is a polynomial time computable function $f\colon\{0,1\}^*\times\{0,1\}^*\rightarrow A_5$ ($A_5$ is the group of all even permutations on 5 positions) and a polynomial $p$ such that $x\in L \iff f(x,0)\circ f(x,1)\circ \cdots\circ f(x,2^{p(x)}-1)=1$, where $\circ$ is multiplication in $A_5$ and $1$ is the identity permutation. Now the sequence of intermediate results of the evaluation of this term can be encoded as an oracle. For all $i=0,1,\dots,2^{p(|x|)}-1$ it has to be checked whether $f(x,i)$ transforms the previous intermediate result into the next one. This is a $\fallp\.\P$ predicate. The two queries, necessary for every $i$, are not of type 1, but one can overcome this difficulty by choosing an appropriate encoding of the queries (cf.~the last step in the proof of our Lemma~\ref{l} below). \end{outline} In \cite{bawa98b} it has been proved that this presentation of $\PSPACE$ and $\NEXPTIME$ cannot be improved with respect to the number of queries. The main goal of this paper is to see if characterizations similar to those above can be provided for small space classes or small depth circuit classes. Before we turn to this point, we first address the class $\NP$. \section{Scaling down and up: NEXPTIME vs.~NP} \label{scaleNP} A known inclusion relating $\NP$ with another class can usually easily be scaled up to obtain a similar result for $\NEXPTIME$. This is done by translational methods (exponential padding). However, here we are interested in going the other direction: ``scaling down''. We have a result for $\NEXPTIME$ such as \begin{align} \label{nexp1} \NEXPTIME &\ =\exz\.\fallp\.\P=\exz[3]\.\fallp\.\P \\ \label{nexp2} &\ =\exz\.\bpp\.\P=\exz\.\corp\.\P \end{align} Can we obtain similar results for $\NP$? What would a ``similar result'' be in this context? One's intuition is to try to reduce logarithmically all of the resource bounds and operator ranges that are involved, and to obtain an equality with the property, that the original result can obtained from the ``scaled down'' result via padding (``scaling up''). However it is clear that this will not work in each case. (We give a concrete example below, showing how some attempts at ``scaling down'' are doomed to failure.) If there is a genuine ``scaled-down'' version of a result, then it cannot be derived mechanically. Rather, it requires a separate proof. In this section we want to exemplify what we mean by comparing some previously-known characterizations of $\NP$ and $\NEXPTIME$. Let us start with an easy example and show how to scale down equation (\ref{nexp1}). \begin{thm}\label{NP3sat} $\NP = \exz\.\falllog\.\P = \exz[3]\.\falllog\.\DLOGTIME$. %\begin{align*} %\NP&=\exz\.\falllog\.\PLT \\ % &= \exz[3]\.\falllog\.\DLOGTIME. %\end{align*} \end{thm} \begin{outline} For the inclusion $\exz\.\falllog\.\P \subseteq \NP$, note that, although a polynomial-time machine $M$ can write queries having a polynomial number of bits (and thus ranging over an exponentially-large address space), for each given oracle and for each given logarithmically-long string $z$, the polynomial-time machine queries at most a polynomial number of oracle positions. Thus, in order to determine if $x$ is in a language in $\exz\.\falllog\.\P$, it suffices to guess a polynomial number of answers in some oracle $A$, and then execute a poly-time machine $M^A(x,z)$ for all of the polynomially-many choices for $z$. For the inclusion $\NP \subseteq \exz[3]\.\falllog\.\DLOGTIME$, the proof relies on the fact that 3-SAT is $\NP$-complete under $\DLOGTIME$-uniform projections %????Is Immerman the best citation for this???? \cite{imm87}. To accept a 3-SAT formula, the existential quantifier guesses an assignment. The universal quantifier guesses a clause. The $\DLOGTIME$ computation checks that the clause is satisfied by the assignment. Since we have 3 literals per clause, we meet the restriction that every $\DLOGTIME$-computation looks at at most 3 bits in the assignment. \end{outline} Sitting inside of Theorem~\ref{NP3sat} is a perfect scaled-down version of equation~(\ref{nexp1}). That is, start with the equality $$\NEXPTIME \ =\exz\.\fallp\.\P=\exz[3]\.\fallp\.\P.$$ When we logarithmically reduce all of the bounding functions, $\NEXPTIME$ becomes $\NP$, $\fallp$ becomes $\falllog$, and $\P$ becomes $\PLT$, to yield the equality $$\NP = \exz\.\falllog\.\PLT = \exz[3]\.\falllog\.\DLOGTIME.$$ It is natural to wonder if the constant ``3'' in Theorem \ref{NP3sat} can be reduced. As the next theorem shows, this is equivalent to the $\NL = \NP$ question. \begin{thm} $\NL = \exz[2]\.\falllog\.\DLOGTIME$. \end{thm} \begin{proof} The proof of $\NL \subseteq \exz[2]\.\falllog\.\DLOGTIME$ relies on the $\NL$-com\-plete\-ness of 2-SAT under DLOGTIME reductions \cite{jon75, imm88b, sze88}. The proof is exactly analogous to that showing that 3-SAT lies in the class $\exz[3]\.\falllog\.\DLOGTIME$. For the other direction, let the values on the oracle tape be $z_i$ (where $1 \le i \le p(n)$ for some polynomial $p$) and let the universally-quantified value be $y$ ($|y| = \log{n}$). Then depending on the input $x$ and on $y$, the machine first looks at one bit on the oracle tape $z_{i_1}$ and depending on whether it is 0 or 1 looks at either $z_{i_2}$ or at $z_{i_3}$ and then accepts or rejects depending on the value of this second bit. All this is done within time $O(\log{n})$. Thus the acceptance criterion can be written as $(z_{i_1} \rightarrow l_2) \wedge (\overline{z_{i_1}} \rightarrow l_3)$, where each $l_j \in \{z_{i_j}, \overline{z_{i_j}}\}$ ($j = 2,3$), which is a 2-SAT formula with 2 clauses. Taking a conjunction over all possible $y$'s we get a 2-SAT formula of polynomial length that is satisfiable iff the machine accepts. Satisfiability of this formula can be checked in ${\rm NL}$, completing the proof. \end{proof} The obvious next step is to ask how to scale down the $\NEXPTIME=\exz\.\BPP=\exz\.\co\RP$ result. Observe that it was just this question which was part of the motivation for the PCP-characterization of $\NP$ \cite{AroraS1998,arlumo+92}, see also \cite{bafolesz91,fglss96,bab93}. The PCP result can be formulated in terms of our operators as follows: \begin{thm}[\cite{AroraS1998,arlumo+92}]\label{PCPthm} $$\NP = \exz\.\bplog\.\P = \exz[O(1)]\.\corlog\.\P.$$ %$$\begin{array}{r@{\ =\ }l} %\NP & \exz\.\bplog\.\P \\& \exz[O(1)]\.\corlog\.\P. %\end{array}$$ \end{thm} Formally scaling down the $\NEXPTIME$ characterization given in equation~(\ref{nexp2}) would yield something like $$\NP \stackrel{?}{=} \exz\.\corlog\.\DLOGTIME$$ or $$\NP \stackrel{?}{=} \exz\.\corlog\.\PLT.$$ {\em Neither} of these equalities hold, as the following proposition demonstrates. \begin{propo}\label{nonprop} $1^* \not\in \exz\.\corlog\.\PLT$. \end{propo} \begin{proof} We essentially follow the proof, given in \cite{fosi88}, that $\co\NP$ is not relativizably contained in $\IP$. Assume $1^*\in \exz\.\corlog\.\PLT$. Let $M$ be the polylogarithmically time-bounded Turing machine such that, on input $1^n$, there exists an oracle $A$ such that for most $y$, $M(x,y,A) = 1$, and such that for any string $x$ that contains any zeros, for any oracle $A$, for most strings $y$, $M(x,y,A) = 0$. Let $n$ be large enough, and consider some ``good'' oracle $A$ that causes $M(x,y,A)$ to accept for most $y$. Given a number $i$ such that $1 \leq i \leq n$, let us say that $i$ {\em is queried by} $y$ if the computation of $M(x,y,A)$ reads bit $i$ of the input. An easy counting argument shows that there is some $i$ such that fewer than one-third of the strings $y$ query $i$. (To see this, note that there are at most $n^k$ possible strings $y$, for some $k$. Each such $y$ queries at most $\log^j{n}$ of the $i$'s. Thus, on average, each $i$ is queried by at most $n^{k-1}/\log^j{n} < n^k/3$ strings $y$.) Thus, $M$ does not have the desired behavior on input $1^{i-1}01^{n-i}$. \end{proof} \begin{remark} It is not hard to show that $\exz\.\corlog\.\DLOGTIME$ does contain $\ntime(\log n)$ (which is equal to $\exz\.\DLOGTIME$). %%%%Right?? -- EWA \end{remark} Thus, it seems at first as if no good options remain to us, in our attempt to scale down equation~(\ref{nexp2}). Theorem \ref{PCPthm} is not adequate, since in scaling up this result, the polynomial time bound becomes an exponential time bound. Instead, we are in need of a stronger PCP-like characterization of $\NP$. As we shall see, this is possible. Fortunately, one can reduce the time bound in Theorem~\ref{PCPthm} to polylogarithmic time if the input is encoded in an error-correcting code, see e.g.~\cite{bafolesz91}, \cite[Theorem 2]{bab93} or \cite[Section 4.8]{hoprst95}. The encoding is a polynomial time procedure, but one can hope that such an encoding is no more time consuming if an additional padding has to be encoded. To make this precise we define {\em polynomial time strong many-one reducibility\/} between sets as follows: Let $A\seq\{0,1\}^*\#^*$. (Later, $\#$ will be our padding symbol.) Then $A\leqms B$ iff there exists a function $f$ with the following properties: First, $f$ is polynomially length bounded. Second, given any string of the form $(x,m)$ ($m$ in binary) we can compute every bit of $f(x\#^m)$ in polynomial time. Finally, $f$ reduces $A$ to $B$, i.e.~$x\#^m\in A \iff f(x\#^m)\in B$. We will use this notion of strong many-one reducibility to define an equivalence relation on complexity classes. Let us write $\K_1\simeq\K_2$ if every set in $\K_1$ is reducible to a set in $\K_2$ by strong many-one reductions, and vice-versa. %??????????NOTE: This is a semantic change over the non-symmetric, %??????????non-transitive relation in the preceding version of the paper. (In most cases of interest to us, we will have $\K_2 \subseteq \K_1$ or vice-versa.) As was pointed out to us by S.~Safra, the proof of the PCP-theorem \cite{arlumo+92} even yields the following stronger characterization of NP: \begin{thm}[\cite{arlumo+92}]\label{PCPthm2} $\NP\simeq \exz[O(1)]\.\corlog\.\PLT$. \end{thm} {From} this statement one can easily conclude (by translation) the MIP theorem $\NEXPTIME=\exz\.\corp\.\P$ (equation~(\ref{nexp2})). The reason for this is the following: Applying standard translational (padding) techniques, given a language $L$ in $\NEXPTIME$, the padded version of $L$, which is in $\NP$, will reduce to a language in $\exz\.\corlog\.\PLT$ under strong many-one reductions. The reduction can actually be performed in time polynomial in the length of the prefix (without padding symbols) which is polylogarithmic in the input length. Translating this up shows $\NEXPTIME\seq\exz\.\corp\.\P$. In fact since we can restrict the number of queries to a constant in Theorem~\ref{PCPthm2} the same applies for $\NEXPTIME$, giving the following improvement of equation~(\ref{nexp2}), already noticed in \cite{gol97}: \begin{coro} $\NEXPTIME=\exz[O(1)]\.\corp\.\P$. \end{coro} \section{Scaling down and up: PSPACE vs.~?}\label{scalepspace} As done for $\NEXPTIME$ in the previous section, we want to examine in this section scaled-down versions of the $\PSPACE$ characterizations {from} Theorem~\ref{ipmip} and \ref{nexppsp}: % \begin{align} \label{psp1} \PSPACE =\ & \exe[2]\.\fallp\.\P = \exe\.\fallp\.\P \\ \label{psp2} \PSPACE =\ & \exe\.\bpp\.\P = \exe\.\corp\.\P \end{align} As in the previous section we have to reduce all resource bounds and operator ranges logarithmically. But what is the scaled-down counterpart $\K$ of $\PSPACE$? When we scale up $\K$ we should arrive at $\PSPACE$, i.e.~for every language $A$, $A\in\PSPACE$ iff there is some $k\in\N$ such that $A_k\in\K$, where $A_k\eqdef\set{x\#^{2^{{|x|}^k}-|x|}}{x\in A}$. It is obvious that every class $\K$ such that $\NCe\seq\K\seq\PLS$ fulfills this condition and hence is a scaled-down counterpart of $\PSPACE$. In fact, we can prove several scaled down versions of equation (\ref{psp1}). Let us start by trying to replace (as in the previous section) the class $\P$ by $\PLT$, i.e., now the class under consideration is the class $\exe[O(1)]\.\falllog\.\PLT$. It turns out that it coincides with %a nondeterministic analogue of %Steve's class $\SC(\eqdef\dtisp(\poly,\polylog))$. That is, it %coincides with the class $\NSC\eqdef\ntisp(\poly,\polylog)$. \begin{thm}\label{pspdown1} $$\begin{array}{rcl} \NSC &=& \exe[3]\.\falllog\.\PLT \\ &=& \exe\.\falllog\.\PLT \\ &=& \exe\.\falllog\.\SC. \end{array} $$ \end{thm} The proof follows immediately from the following two lemmas. \begin{lemma}\label{lshamir} For every $s$ such that $\log n\leq s(n)\leq\poly$, we have $$\exe\.\falllog\.\dtisp(\poly,s)\seq\ntisp(\poly,s).$$ \end{lemma} \begin{proof} The proof is similar to the proof of $\IP\seq\PSPACE$. We simulate a computation of the form $\exe\.\falllog\.\dtisp(\poly,s)$ by making a depth first search in the query tree. Note that, since the length of a query must respect the space bound, a query consists of $O(s)$ bits. Furthermore, since the oracle's access is of type 1, there are at most $O(s)$ queries made on any execution path. Thus a query-answer sequence can be stored in $O(s)$ space. In order to search the query tree, we first guess a query-answer sequence and check that it is the leftmost one in the tree of all possible such sequences. (That is, it is the sequence generated if all of the oracle queries are answered negatively.) Then we check that if this is a sequence that actually occurs on one path of the $\falllog\.\dtisp(\poly,s)$ computation, then this computation path is accepting. That is, we cycle through all possible strings $y$ of length $\log n$, and verify that {\em either} $M(x,y)$ does {\em not} ask the queries in that sequence, {\em or} (it {\em does} ask that sequence, {\em and} it accepts). Next, we consider the lexicographically next queries-answer-sequence, check again that if it actually occurs it leads to an accepting computation. In this way we search the whole query tree. All in all we guess an oracle, but since access to this oracle is type 1, we only have to store one path in the tree in order to be able to be consistent with previous answers (we do not have to store the whole oracle up to the maximal query length). Thus the simulation is space bounded by $s(n)$ and since $s$ is bounded by a polynomial and we have only polynomially many $\falllog\.\dtisp(\poly,s)$ computations, the overall time is also polynomial. \end{proof} \begin{lemma}\label{l} $$\ntisp(\poly,\log^k)\seq \exe[3]\.\falllog\.\dtime(\log^{k+1}).$$ \end{lemma} \begin{proof} The proof consists of two main ingredients: First, after observing that any language in $\ntisp(\poly,\log^k)$ is accepted in these resource bounds by an ``oblivious'' machine (whose input head continually sweeps back and forth across the input tape), we show that any such language is accepted by small-width nondeterministic circuits. Next, we show that such circuits can be simulated in $\exe[3]\.\falllog\.\dtime(\log^{k+1})$. The main point here is that we have to force type 1 behavior while simulating the circuit. Let $A\in\ntisp(\poly,\log^k)$ be recognized by machine $M$ whose input head sweeps back and forth across its input tape. (It has been observed before that this is no loss of generality \cite{pippenger.fischer}.) Now a straightforward modification of an argument of Pippenger \cite{pippenger} shows that $A$ is accepted by a \DLOGTIME-uniform family of circuits $\{C_n\}$ of the following form: \begin{itemize} \item $C_n$ consists of $O(n^a\log^k n)$ gates arranged in $n^a$ levels, where gates at level $i$ are either input gates or are connected to at most two gates at level $i-1$. \item Each level $i$ has $O(\log^k n)$ gates, of which exactly one is a ``regular'' input gate, and one is a ``nondeterministic'' input gate. Each ``regular'' input gate is connected to some bit of the input string $x$ (and each bit of the input can be read at several different levels). In contrast, each ``nondeterministic'' gate is completely independent of all other nondeterministic gates. That is, the nondeterministic bits have a ``read once'' property. \item $x$ is in $A$ if and only if there is a setting of the nondeterministic gates that causes $C_n$ to output 1 on input $x$. \end{itemize} It is easy to see how to construct these circuits. The gates at level $i$ encode the worktape configuration of $M$ at time $i$ along a computation path. It is also easy to see that these circuits give an alternate characterization of $\NSC^k$, in the sense that a language is in $\NSC^k$ if and only if $A$ is accepted by a circuit family of this type. It remains only to show that $A$ is in $\exe[3]\.\falllog\.\dtime(\log^{k+1})$. Let $x$ be a string of length $n$, and let $m$ be the number of gates in $C_n$ (including the nondeterministic gates and the input gates). Without loss of generality, let the gates of $C_n$ have names of the form $(i,j)$ where $i$ denotes the level on which the gate is located, and $j = O(\log^k n)$. Furthermore, let $(i,1)$ be the input gate on level $i$, and let $(i,2)$ be the nondeterministic gate on level $i$. Let the output gate of $C_n$ be $(n^a,3)$. Given a vector $b$ of length $m$ (where $b$ should be thought of as a list of values for each gate of $C_n$), let $b(i,j)$ denote the value of bit $(i,j)$ of $b$ (i.e., the value that $b$ records for gate $(i,j)$). Note that $x$ is in $A$ if and only if \begin{itemize} \item there is vector $b$ of length $m$ such that for all $(i,j)$ \begin{itemize} \item $b(i,1)$ is equal to the appropriate bit of $x$, and \item If $i=1$ then $b(1,j)$ encodes the $j$th bit of the initial configuration. \item If $i > 1$ then the value of $b(i,j)$ is consistent with the values of its (at most two) predecessors on level $i-1$. \item If $i=n^a$ then $b(i,3) = 1$. \end{itemize} \end{itemize} It is clear that this computation can be accomplished in $\exz[3]\.\falllog\dtime(\log)$ because $C_n$ is $\DLOGTIME$-uniform, and a deterministic machine can check if the bits of oracle $b$ satisfy the stated conditions for any given $(i,j)$. However, we need to carry out this simulationn with only type 1 access to the oracle. In order to do this, we will have to use a different encoding of the vector $b$. Let $b(i)$ denote the segment $b(i,1), b(i,2),\ldots$ of length $O(\log^k n)$ corresponding to level $i$. Thus $b = b(0)b(1)\ldots b(n^a)$. Observe that it will suffice if we can devise an oracle encoding of $b$ so that a $\dtime(\log^k)$ machine on input $(x,(i,j))$ can obtain bits from $b(i)$ and $b(i-1)$ in a type 1 manner. Let $2^v$ be the smallest power of $2$ greater than $n^a$. The string $b$ contains $b(i)$ for $i \leq n^a$; for completeness define $b(i) \eqdef 0...000$ for $n^a < i < 2^v$. Construct an oracle $B$ as follows: Given $i$, $1\leq i< 2^v$, we want to encode $b(i)$ into $B$ by putting one string into the oracle for every bit in $b(i)$ that is $1$. First, let the length $v$ binary representation of $i$ be $u_1\cdots u_{\ell-1}u_{\ell}10^q$. Let $b(i)=b_1b_2\cdots b_c$. Then for every $1\leq j\leq c$, put the string $0^cu_10^cu_20^c \cdots 0^cu_{\ell}0^j$ into $B$ iff $b_j=1$. Then we can recover $b(i,j)$ by asking the oracle for $0^cu_10^cu_20^c \cdots 0^cu_{\ell}0^j$. Moreover, the reader can easily verify that for any choice of $i$ and $j_1, j_2, j_3$ with $j_1 < j_2$, it is either the case that the oracle addresses encoding $b(i-1,j_1), b(i-1,j_2), b(i,j_3)$ can be queried in a type 1 manner (in that order), or else the ordering $b(i,j_3), b(i-1,j_1), b(i-1,j_2)$ will work. The length of the oracle queries is now bounded by $O(\log^{k+1}n)$, and this is the dominant term in the running time. \end{proof} %Defining $\SC^k\eqdef\dtisp(\poly,\log^kn)$ and %$\NSC^k\eqdef\ntisp(\poly,\log^kn)$ we thus have: \begin{coro} $\NSC^k \seq \exe[3]\.\falllog\.\dtime(\log^{k+1}n) \seq \exe\.\falllog\.\SC^{k+1} \seq \NSC^{k+1}$. %$$\begin{array}{r@{\ \seq\ }l} %\NSC^k & \exe[3]\.\falllog\.\dtime(\log^{k+1}) \\ % & \exe\.\falllog\.\SC^{k+1} \\ % & \NSC^{k+1}. %\end{array} %$$ \end{coro} Since $\NSC$ is a scaled-down counterpart of $\PSPACE$, the result $\NSC = \exe[3]\.\falllog\.\PLT$ (Theorem \ref{pspdown1}) is a perfect scaled-down analogue of $\PSPACE = \exe[2]\.\fallp\.\P$ (equation (\ref{psp1})), except that we need one oracle query more in our $\NSC$ characterization. It is now natural to ask what happens if in the above we replace $\PLT$ by $\DLOGTIME$. This leads us to a second scaled-down analogue of equation (\ref{psp1}) as follows: \begin{thm}\label{pspdown2} $$\begin{array}{rcl} \NCe &=& \exe[2]\.\falllog\.\DLOGTIME \\ &=& \exe\.\falllog\.\DLOGTIME \end{array} $$ \end{thm} \begin{proof} The inclusion $\NCe \seq \exe[2]\.\falllog\.\DLOGTIME$ is essentially Barrington's Theorem \cite{bar89}. Barrington showed that for every $A\in\NCe$ there is a function $f\colon\{0,1\}^*\times\{0,1\}^*\rightarrow A_5$ computable in logarithmic time and a polynomial $p$ such that for all $x$, $$x\in A \iff f(x,0)\circ f(x,1) \circ\cdots\circ f(x,p(|x|)) = 1.$$ The proof now is similar to that of Theorem~\ref{nexppsp}.2. As in the above proof, the sequence of intermediate results of the evaluation of this term can be encoded as an oracle. For all $i=0,1,\dots,p(|x|)$ it has to be checked whether $f(x,i)$ transforms the previous intermediate result into the next one. This is a $\falllog\.\DLOGTIME$ predicate with two oracle queries. Without further care however, the two necessary queries for every $i$ are not of type 1, but one can overcome this difficulty by choosing an appropriate encoding of the queries and making use of the tree rearranging techniques employed in Lemma~\ref{l}. To complete the proof, it remains to show that $\exe\.\falllog\.\DLOGTIME \seq \NCe$. We actually prove a somewhat more general result in the following lemma. \end{proof} \begin{lemma}\label{nceo} Let $\cal C$ be either $\L$ or $\DLOGTIME$. Then each language $A$ in $\exe\.\falllog\.{\cal C}$ is accepted by a family of $\NCe$ circuits with oracle gates for a language from $\cal C$. \end{lemma} \begin{proof} Let $A$ be in $\exe\.\falllog\.{\cal C}$, as witnessed by some machine $M$. That is, for a string $x$ of length $n$, $x$ is in $A$ if and only if $\exe B$ such that, for all strings $z$ of length $\log n$, $M^B(x,z)$ accepts. Recall that the oracle queries that are asked must be short enough to fit on $M$'s tape (which is subject to the logarithmic space bound). Since $M$ is a deterministic machine, for any given computation of $M^B(x,z)$, there is a string $i$ of length $\log n$ such that the set of queries that are asked by machine $M$ during the computation are a subset of \{$j : j$ is a prefix of $i$\}. Thus the condition ``$M^B(x,z)$ accepts'' can be rewritten as follows: for all strings $i$ of length $\log n$, either some query asked by $M^B(x,z)$ is {\em not} a prefix of $i$, or all queries asked by $M^B(x,z)$ {\em are} prefices of $i$, and $M^B(x,z)$ accepts. For an oracle $B$ and a string $i$, let $\vec{B(i)}$ denote the sequence of length $|i|+1$ consisting of the answers to all queries of the form ``is $j$ in $B$?'' where $j$ is a prefix of $i$ (including the empty prefix). Let $[M,x,z,i,\vec{B(i)}]$ denote the Boolean value of the condition ``either some query asked by $M^B(x,z)$ is {\em not} a prefix of $i$, or all queries asked by $M^B(x,z)$ {\em are} prefices of $i$, and $M^B(x,z)$ accepts''. (Note that this condition depends only on the bits that are present in $\vec{B(i)}$.) Restating, note that $x$ is in $A$ if and only if \[\exe B \falllog z \falllog i [M,x,z,i,\vec{B(i)}]\] which is equivalent to \[\exe B \falllog i \falllog z [M,x,z,i,\vec{B(i)}].\] Let us pick the value of $B(\emptystring)$ nondeterministically. Thus \[\exe B \falllog i \falllog z [M,x,z,i,\vec{B(i)}]\] is equivalent to \[\exists b\in\{0,1\}\ \exe B' \falllog i \falllog z [M,x,z,i,b\vec{B'(i)}], \] where $[M,x,z,i,b\vec{B'(i)}]$ means the same thing as $[M,x,z,i,\vec{B'(i)}]$, except the value $b$ is used in place of the first bit $B(\emptystring)$ of $\vec{B'(i)}$ when answering the oracle queries asked by $M$. Next note that, if the first bit of $i$ is 0, then the value of $[M,x,z,i,b\vec{B'(i)}]$ is completely independent of the value of $B(1)$, and similarly if the first bit of $i$ is 1, then the value of $[M,x,z,i,b\vec{B'(i)}]$ is completely independent of the value of $B(0)$. Thus we can pick the answers to these queries to $B$ independently. That is, the expression \[\exe B \falllog i \falllog z [M,x,z,i,\vec{B(i)}]\] is equivalent to \begin{multline*} \exists b\in\{0,1\}\ \forall c\in\{0,1\}\ \exists b' \in \{0,1\}\\ \exe B' \forall i\in c\{0,1\}^{\log n - 1} \falllog z [M,x,z,i,bb'\vec{B(i)}]. \end{multline*} This process can be extended for $\log n$ steps, where we first existentially guess a value for $B(j)$ (for some prefix $j$ of our current $i$) and then universally check that the guess is good for both extensions $j0$ and $j1$ of $j$. This gives a ($\DLOGTIME$-uniform) formula for this expression, where the atomic predicates of the formula are of the form $[M,x,z,\alpha]$ for some logarithmic-length string $\alpha$. The condition $[M,x,z,\alpha]$ can be answered by an oracle gate for a language in $\cal C$. This completes the proof. \end{proof} Theorem~\ref{pspdown1} showed that applied to $\SC$ the quantifier sequences $\exe\.\falllog$ and $\exe[O(1)]\.\falllog$ add exactly the power of nondeterminism. For the case of logarithmic space computations however the situation is different: \begin{thm}\label{lthm} $$\begin{array}{rcl} \L &=& \exe[O(1)]\.\falllog\.\L \\ &=& \exe\.\falllog\.\L \end{array} $$ \end{thm} \begin{proof} The inclusions from left to right are obvious. The other direction follows from Lemma~\ref{nceo} above. \end{proof} Comparing Theorems \ref{pspdown1} and \ref{lthm}, the reader may be tempted to conclude that if $\L = \SC$, then $\L = \NSC$, reasoning as follows: $\L = \exe\.\falllog\.\L = \exe\.\falllog\.\SC = \NSC.$ In fact, no such implication is known to hold. The flaw in the one-line ``proof'' lies in the fact that the hypothesized equality $\L = \SC$ (concerning two unrelativized classes) does {\em not} imply that the ``relativized classes of type 10'' $\L$ and $\SC$ are equal. (See Definition \ref{relclass} regarding relativized classes of type $\sigma_1\sigma_2$.) In fact, a simple diagonalization argument shows that these relativized classes are {\em not} equal. \section{Conclusion} In this paper, we presented a number of characterizations of the classes $\NCe$, $\L$, $\NL$, and $\NSC$ in terms of oracle operators. In all our results, we addressed the question what number of queries is actually necessary. A number of questions remain open. First, we want to discuss the question about a scaled-down version of equation (\ref{psp2}). {From} the discussion at the beginning of Sect.~\ref{scalepspace}, it is clear that to show $\NCe \seq \exe\.\bplog\.\DLOGTIME \seq \exe\.\bplog \PLT \seq\PLS$ is sufficient to obtain (\ref{psp2}) by translation. However the power of the operator sequence $\exe\.\bplog$ is not clear to us. Concerning upper bounds, $\exe\.\bplog\.\SC \seq \NSC$ can be shown as in the proof of Lemma~\ref{lshamir}. In fact one can even observe that the simulation given there constitutes a symmetric algorithm, showing that $\exe\.\bplog\.\L\seq\SymL$. Concerning lower bounds, inclusions as $\NCe\seq\exe\.\bplog\.\PLT$ are not very likely for the same reasons as explained in Section \ref{scaleNP} (see the discussion preceding Proposition~\ref{nonprop}). However one might hope for $\NCe\leqms\exe\.\bplog\.\PLT$, but this is open. Let us therefore conclude with the question if one of the classes $\exe\.\bplog\.\SC$, $\exe\.\bplog\.\L$, $\exe\.\bplog\.\PLT$, or $\exe\.\bplog\.\DLOGTIME$ coincides with well-known classes. A second question concerns the relation of our Proposition~\ref{nonprop} with the relativization result in \cite{fosi88}. Can a general correspondence between \mbox{(poly-)} logtime classes from our context and relativized polynomial time classes, perhaps along the lines of \cite{bocrsi92,ver93a}, be obtained? %The answer is YES, but this is not the content of the present paper. \bigskip \noindent{\bf Acknowledgment.} We thank S.~Safra for pointing out that the proof of the PCP-theorem {from} \cite{arlumo+92} yields Theorem~\ref{PCPthm2}. We also thank the referee for suggesting improvements to the proof of Lemma \ref{l}. \bibliography{AADVW} \bibliographystyle{alpha} \end{document}