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