% The Chicago Journal of Theoretical Computer Science, Volume 1995, Article 1
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1995 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,published]{cjstruct}
\else
\documentclass[v1.1,published]{cjstruct}
\fi
%
% Local macro definitions for this article.
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
\ifltwoe\else\newcommand{\textsl}[1]{{\sl #1\/}}\fi
\ifltwoe\else\newcommand{\textbf}[1]{{\bf #1}}\fi
%
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
%
\mathstyleclass{\complexityclass}{\mathord}{\textsl}
\mathstyleclass{\functionclass}{\mathord}{\textit}
\mathstyleclass{\function}{\mathord}{\textit}
\newcommand{\complement}[1]{\mathord{\mbox{\sl co\begin{math}#1\end{math}}}}
\newcommand{\logicequiv}{\Longleftrightarrow}
\newcommand{\logicimplies}{\Longrightarrow}
\newcommand{\logicimplied}{\Longleftarrow}
\newcommand{\logicand}{\wedge}
\newcommand{\logicor}{\vee}
\newcommand{\logicnot}{\neg}
\newcommand{\logiciteror}{\bigvee}
\newcommand{\setsize}[1]{\left|#1\right|}
\newcommand{\condval}[1]{\left\{\begin{array}{ll}#1\end{array}\right.}
\newcommand{\setof}[2]{\{\,#1\mid#2\,\}}
\newcommand{\bigsetof}[2]{\bigl\{\,#1\bigm|#2\,\bigr\}}
\newcommand{\orderof}[1]{O(#1)}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\graphedge}[2]{#1\mathord{\rightarrow}#2}
\newcommand{\compclsum}[1]{\bigoplus#1}
\newcommand{\oftype}{\mathpunct{:}}
\newcommand{\mult}{\cdot}
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1995, Article 1\\
      \textit{30 June, 1995}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{gopher.mit.edu}
    \item \emph{gopher.cs.uchicago.edu}
    \item anonymous \emph{ftp} at \emph{mitpress.mit.edu}
    \item anonymous \emph{ftp} at \emph{cs.uchicago.edu}
  \end{itemize}
\sentence
}
%
\copyrightstmt{%
  \copyright 1995 by Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The \emph{Chicago Journal of Theoretical Computer Science\/}
  is a peer-reviewed scholarly
  journal in theoretical computer science\@. The journal is committed
  to providing a forum for significant results on theoretical
  aspects of all topics in Computer Science\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Stephen Homer & Alan Selman \\
        Jin-Yi Cai & Neil Immerman & Nir Shavit \\
        Anne Condon & Paris Kanellakis & Eva Tardos \\
        Cynthia Dwork & Howard Karloff & Sam Toueg \\ 
        David Eppstein & Philip Klein & Moshe Vardi \\
        Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
        Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
        Steven Fortune & Michael Merritt
      \end{tabular}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1995}
%
\articleid{1}
%
\selfcitation{
     @article{cj95-01,
       author={Noam Nisan and Amnon Ta-Shma},
       title={Symmetric \(\mbox{\textsl{Logspace}}\) is Closed Under
         Complement},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1995},
       number={1},
       publisher={MIT Press},
       month={June},
       year={1995}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\editorname{Stuart A.\ Kurtz}
%
\title{Symmetric \protect\(\complexityclass{Logspace}\protect\)
  is Closed Under Complement}
\shorttitle{Symmetric \protect\(\complexityclass{Logspace}\protect\)}
\collectiontitle{}
\begin{authorinfo}
   \printname{Noam Nisan}
   \collname{}{Nisan, Noam}
   \begin{institutioninfo}
       \instname{Hebrew University}
       \department{Institute of Computer Science}
       \address{}{Jerusalem}{}{Israel}{}
   \end{institutioninfo}
   \email{noam@cs.huji.ac.il}
\end{authorinfo}
%
\begin{authorinfo}
   \printname{Amnon Ta-Shma}
   \collname{}{Ta-Shma, Amnon}
   \begin{institutioninfo}
       \instname{Hebrew University}
       \department{Institute of Computer Science}
       \address{}{Jerusalem}{}{Israel}{}
   \end{institutioninfo}
   \email{am@cs.huji.ac.il}
\end{authorinfo}
%
\shortauthors{Nisan and Ta-Shma}
%
\support{%
  This work was supported by BSF Grant 92-00043 and by a Wolfeson
  Award administered by the Israeli Academy of Sciences\@. The work
  was revised while visiting BRICS, Basic Research in Computer
  Science, Centre of the Danish National Research Foundation. A
  preliminary version of this paper appeared in the proceedings of the
  \emph{27th Annual ACM Symposium on the Theory of Computing, 1995}\@.
}
%
\begin{editinfo}
\submitted{18}{11}{1994}\reported{30}{3}{1995}
\submitted{4}{4}{1995}\reported{5}{4}{1995}
\submitted{7}{4}{1995}\reported{19}{5}{1995}\published{30}{6}{1995}
\end{editinfo}
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
\apar{Abstract-1}
We present a \(\complexityclass{Logspace}\), many-one reduction from
the undirected \mbox{\(s\)--\(t\)} connectivity problem to its
complement\@. This shows that
\(\complexityclass{SL}=\complement{\complexityclass{SL}}\)\@.
\end{abstract}
%
\asection{1}{Introduction}
%
\apar{1-1}
This paper deals with the complexity class symmetric
\(\complexityclass{Logspace}\), \(\complexityclass{SL}\), defined by
Lewis and Papadimitriou in \cite{cj95-01-9}\@. This class can be defined
in several equivalent ways:
%
\begin{enumerate}
%
\item[1.] Languages that can be recognized by symmetric, nondeterministic
Turing Machines that run within logarithmic space\@.  See \cite{cj95-01-9}\@.
%
\item[2.] Languages that can be accepted by a uniform family of polynomial-size
contact schemes (these may also be called switching networks)\@.
See \cite{cj95-01-12}\@.
%
\item[3.] Languages that can be reduced in
\(\complexityclass{Logspace}\) via a many-one reduction
to \(\complexityclass{USTCON}\), the undirected \(s\)--\(t\)
connectivity problem\@.
%
\end{enumerate}
\sentence
%
\apar{1-2}
A major reason for the interest in this class is that it captures the
complexity of \(\complexityclass{USTCON}\)\@. The input to
\(\complexityclass{USTCON}\) is an undirected graph \(G\), and two
vertices in it, \(s\) and \(t\)\@. The input should be accepted if
\(s\) and \(t\) are connected via a path in \(G\)\@. The similar
problem \(\complexityclass{STCON}\), where the graph \(G\) has
directed edges, is complete for non-deterministic
\(\complexityclass{Logspace}\) (\(\complexityclass{NL}\))\@. Several
combinatorial problems are known to be in \(\complexityclass{SL}\) or
\(\complement{\complexityclass{SL}}\) (e.g., \(2\)-colorability is
complete for \(\complement{\complexityclass{SL}}\) \cite{cj95-01-13})\@.
%
\apar{1-3}
The following facts are known regarding \(\complexityclass{SL}\)
relative to other complexity classes in ``the vicinity'':
%
\[
  \complexityclass{L}\subseteq\complexityclass{SL}\subseteq
  \complexityclass{RL}\subseteq\complexityclass{NL}
\]
\sentence
%
Here, \(\complexityclass{L}\) is the class deterministic
\(\complexityclass{Logspace}\) and \(\complexityclass{RL}\) is the
class of problems that can be accepted with one-sided error by a
randomized \(\complexityclass{Logspace}\) machine running in
polynomial time\@. The containment
\(\complexityclass{SL}\subseteq\complexityclass{RL}\) is the only
non-trivial one in the line above and follows directly from the randomized
\(\complexityclass{Logspace}\) algorithm for
\(\complexityclass{USTCON}\) of \cite{cj95-01-2}\@. It is also known that
\(\complexityclass{SL}\subseteq\complexityclass{SC}\) \cite{cj95-01-10},
\(\complexityclass{SL}\subseteq\compclsum{\complexityclass{L}}\)
\cite{cj95-01-8}, and
\(\complexityclass{SL}\subseteq\complexityclass{DSPACE}(\log^{1.5}n)\)
\cite{cj95-01-11}\@.
%
\apar{1-4}
After the surprising proofs that \(\complexityclass{NL}\) is closed
under complement were found \cite{cj95-01-6,cj95-01-16}, Borodin et
al.\ \cite{cj95-01-4} asked whether the same is true for
\(\complexityclass{SL}\)\@. They could prove only the weaker
statement, namely that \(\complexityclass{SL} \subseteq
\complement{\complexityclass{RL}}\), and left
``\(\complexityclass{SL}=\complement{\complexityclass{SL}}\)?'' as an
open problem\@. In this paper we solve the problem in the affirmative
by exhibiting a \(\complexityclass{Logspace}\), many-one reduction
from \(\complexityclass{USTCON}\) to its complement\@. Quite
surprisingly, the proof of our theorem does not use inductive
counting, as do the proofs of
\(\complexityclass{NL}=\complement{\complexityclass{NL}}\)\@. This is
a simpler proof than Borodin's, et al.; however, it uses
the \cite{cj95-01-1} sorting networks\@.
%
\begin{alabsubtext}{Theorem}{1}{}
  \(\complexityclass{SL}=\complement{\complexityclass{SL}}\)
\sentence
\end{alabsubtext}
%
It should be noted that the monotone analogs (see \cite{cj95-01-5})
of \(\complexityclass{SL}\) and \(\complement{\complexityclass{SL}}\)
are known to be different \cite{cj95-01-7}\@.
%
\apar{1-5}
As a direct corollary of our theorem, we obtain
\(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}=
  \complexityclass{SL}\)
where \(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}\) is
the class of languages accepted by \(\complexityclass{Logspace}\)
oracle Turing machines with oracle from \(\complexityclass{SL}\),
using the oracle model of \cite{cj95-01-14}\@.
%
\begin{alabsubtext}{Corollary}{1.1}{}
  \(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}=
  \complexityclass{SL}\)
\sentence
\end{alabsubtext}
%
\apar{1-6}
In particular, we show that both ``symmetric
\(\complexityclass{Logspace}\) hierarchies'' (the one defined by
alternation in \cite{cj95-01-13} and the one defined by oracle queries
in \cite{cj95-01-3}) collapse to \(\complexityclass{SL}\)\@.
%
\asection{2}{Proof of Theorem}
%
\asubsection{2.1}{Overview of proof}
%
\apar{2.1-1}
We design a many-one reduction from \(\complexityclass{coUSTCON}\) to
\(\complexityclass{USTCON}\)\@. We start by developing simple tools
for combining reductions in subsection~2.2\@. In
particular, these tools will allow us to use the AKS sorting networks
in order to ``count\@.'' At this point, the main ingredient of the
reduction will be the calculation of the number of the connected
components of a graph\@. An upper bound to this number is easily
obtained using transitive closure, while the main idea of the proof is
to obtain a lower bound by computing a spanning forest of the graph\@.
We do this in subsection~2.3\@. Everything is put
together in subsection~2.4\@.
%
\asubsection{2.2}{Projections to
  \protect\(\protect\complexityclass{USTCON}\protect\)}
%
\apar{2.2-1}
In this paper we will use only the simplest kind of reductions (i.e.,
\(\complexityclass{Logspace}\)-uniform projection
reductions \cite{cj95-01-15})\@. Moreover, we will be interested only
in reductions to \(\complexityclass{USTCON}\)\@. We define this kind
of reduction and we show some of its basic properties in this
subsection\@.
%
\begin{alabsubtext}{Notation}{2.1}{}
  Given \(f\oftype\funcspace{\{0,1\}^*}{\{0,1\}^*}\), denote by
  \(f_n\oftype\funcspace{\{0,1\}^n}{\{0,1\}^*}\) the restriction of \(f\) to
  inputs of length \(n\)\@. Denote by \(f_{n,k}\) the \(k\)th bit
  function of \(f_n\) (i.e., if
  \(f_n\oftype\funcspace{\{0,1\}^n}{\{0,1\}^m}\), then
  \(f_n(\vec{x})=(f_{n,1}(\vec{x}),\ldots,f_{n,m}(\vec{x}))\))\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Notation}{2.2}{}
  We represent an \(n\)-node undirected graph \(G\) using \(n\choose
  2\) variables \(\vec{x}=(x_{i,j})_{1\le i<j\le n}\) s.t.\ 
  \(x_{i,j}\) is \(1\) iff \((i,j)\in E(G)\)\@. If \(f(\vec{x})\)
  operates on graphs, we will write \(f(G)\), meaning that the input
  to \(f\) is a binary vector of length \(n\choose 2\) representing
  \(G\)\@.
\end{alabsubtext}
%
\apar{2.2-2}
{\sloppy
We say that \(f\oftype\funcspace{\{0,1\}^*}{\{0,1\}^*}\) reduces to
\(\complexityclass{USTCON}(m)\) if we can, uniformly and in
\(\complexityclass{Logspace}\), label the edges of a graph of size
\(m\) with \({\setof{0,1,x_i,\logicnot x_i}{1\le i\le n}}\), s.t.\ 
\(f_{n,k}(\vec{x})=1\) if and only if there is a path from \(1\) to
\(k\) in the corresponding graph\@. We may formalize this with a
definition\@.
\par}
%
\begin{alabsubtext}{Definition}{2.1}{}
  We say that \(f\oftype\funcspace{\{0,1\}^*}{\{0,1\}^*}\) reduces to
  \(\complexityclass{USTCON}(m)\), \(m=m(n)\), if there is a uniform
  family of \(\complexityclass{Space}(log(n))\) functions
  \(\{\sigma_{n,k}\}\) s.t.\ for all \(n\) and \(k\):
%
\begin{itemize}
%
\item \(\sigma_{n,k}\) is a projection (i.e., \(\sigma_{n,k}\) is a
  mapping from \({\bigsetof{\{i,j\}}{1\leq i<j\leq m}}\) to
  \(\setof{0,1,x_i,\logicnot x_i}{1\le i\le n}\))\@. We abuse the notation
  by writing \(\sigma_{n,k}(i,j)\) instead of
  \(\sigma_{n,k}(\{i,j\})\)\@.
%
\item Given \(\vec{x}\) define \(G_{\vec{x},k}\) to be the graph
  \(G_{\vec{x},k}=(\{1,\ldots,m\},E)\) where\\ 
  \begin{eqnarray*}
    E=\bigsetof{(i,j)&}{&\sigma_{n,k}(i,j)=1\mathrel{\mbox{ or }}
      \bigl(\sigma_{n,k}(i,j)=x_i\mathrel{\mbox{ and }}x_i=1\bigr)\\
    &&\mathrel{\mbox{ or }}\bigl(\sigma_{n,k}(i,j)=\logicnot x_i
      \mathrel{\mbox{ and }}x_i=0\bigr)}
  \end{eqnarray*}
  \sentence
%
\item \(f_{n,k}(\vec{x})=1 \logicequiv\mbox{ there is a path from }1
  \mbox{ to }m\mbox{ in }G_{\vec{x},k}\)\@.
%
\end{itemize}
\sentence
%
  If \(\sigma\) is restricted to the set \(\setof{0,1,x_i}{1\le i\le n}\),
  we say that \(f\) \emph{monotonically} reduces to
  \(\complexityclass{USTCON}(m)\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{2.1}{}
  If \(f\) has uniform monotone formulae of size \(s(n)\), then \(f\) is
  monotonically reducible to
  \(\complexityclass{USTCON}(\orderof{s(n)})\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.1}{}
\prooffontshape
%
  Given a formula \(\phi\), recursively build \((G,s,t)\) as follows:
\begin{itemize}
\item If \(\phi=x_i\), then build a graph with two vertices \(s\) and
  \(t\) and one edge between them labeled \(x_i\)\@.
\item If \(\phi=\phi_1\logicand\phi_2\), and \((G_i,s_i,t_i)\), then
  the graphs for \(\phi_i\), \(i=1,2\) identify \(s_2\) with \(t_1\),
  and define \(s=s_1,t=t_2\)\@.
\item If \(\phi=\phi_1\logicor\phi_2\), and \((G_i,s_i,t_i)\),
  then the graphs for \(\phi_i\), \(i=1,2\) identify \(s_1\) with
  \(t_1\) and \(s_2\) with \(t_2\), and define \(s=s_1=t_1\) and
  \(t=s_2=t_2\)\@.
\end{itemize}
\sentence
%
{\samepage\markendlst{Proof of Lemma 2.1}}
\end{alabsubtext}
%
\apar{2.2-3}
%
\begin{alabsubtext}{Definition}{2.2}{}
  \(\function{Sort}\oftype\funcspace{\{0,1\}^n}{\{0,1\}^n}\) is the Boolean
  sorting function (i.e., it moves all the zeros to the beginning of
  the string)\@.
\end{alabsubtext}
%
Using the \(AKS\) sorting networks \cite{cj95-01-1}, which belong to
\(\complexityclass{NC}^1\), we derive the following corollary\@.
%
\begin{alabsubtext}{Corollary}{2.2}{}
  \(\function{Sort}\) is monotonically reducible to
  \(\complexityclass{USTCON}(\functionclass{poly})\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{2.3}{}
  If \(f\) monotonically reduces to \(\complexityclass{USTCON}(m_1)\),
  and \(g\) reduces to \(\complexityclass{USTCON}(m_2)\), then
  \(f\circ g\) reduces to \(\complexityclass{USTCON}(m_1^2\mult m_2)\),
  where \(\circ\) is the standard function composition operator\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.3}{}
\prooffontshape
%
  The function \(f\) monotonically reduces to a graph with \(m_1\)
  vertices, where each edge is labeled with one of \(\{0,1,x_i\}\)\@.
  In the composition function \(f\circ g\), each \(x_i\) is replaced
  by \(x_i=g_i(\vec{y})\), which can be reduced to a connectivity
  problem of size \(m_2\)\@. Replace each edge labeled \(x_i\) with
  its corresponding connectivity problem\@. There can be \(m_1^2\)
  edges, each replaced by a graph with \(m_2\) vertices\@. The
  resulting new graph has \(m_1^2 \mult m_2\) vertices\@.
%
{\samepage\markendlst{Proof of Lemma 2.3}}
\end{alabsubtext}
%
\asubsection{2.3}{Finding a spanning forest}
%
\apar{2.3-1} We show how to build a spanning forest using
\(\complexityclass{USTCON}\) in this section\@. Reif \cite{cj95-01-13}, and
independently, Cook, have previously noted this idea\@.
%
\apar{2.3-2} Given a graph \(G\), index the edges from \(1\) to
\(m\)\@. We can view the indices as weights to the edges, and, as no
two edges have the same weight, we know that there is a unique minimal
spanning forest \(F\)\@. In our case, where the edges are indexed,
this minimal forest is the lexicographically first spanning forest\@.
\apar{2.3-3} It is well known that the greedy algorithm finds a
minimal spanning forest\@. Let us recall how the greedy algorithm
works in our case\@. The algorithm builds a spanning forest \(F\)
which is empty at the beginning, \(F=\emptyset\)\@. Then the
algorithm checks the edges one by one according to their order\@. For
each edge \(e\), if \(e\) does not close a cycle in \(F\), then \(e\)
is added to the forest\@. This may be stated as \(F=F\cup\{e\}\)\@.
%
\apar{2.3-4}
At first glance, the algorithm looks sequential\@. However,
claim~2.4.1 shows that the greedy algorithm is actually
highly parallel\@. To check whether an edge participates in the
forest, we need only one \(s\)--\(t\) connectivity problem over an
easily-obtainable graph\@.
%
\begin{alabsubtext}{Definition}{2.3}{}
  For an undirected graph \(G\) denote by \(\function{LFF}(G)\) the
  lexicographically first spanning forest of \(G\)\@. Let
  \(\function{SF}(G)\in\{0,1\}^{n\choose 2}\) be:
\[
\function{SF}_{i,j}(G)=
  \condval{%
    0 & (i,j)\in\function{LFF}(G) \\
    1 & \mbox{otherwise}
  }
\]
\sentence
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{2.4}{}
  \(\function{SF}\) reduces to
  \(\complexityclass{USTCON}(\functionclass{poly})\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.4}{}
\prooffontshape
%
  Let \(F\) be the lexicographically first spanning forest of \(G\)\@.
  For \(~e \in E\), define \(G_e\) to be the subgraph of \(G\)
  containing only the edges
  \(\setof{e'\in E}{\function{index}(e')<\function{index}(e)}\)\@.
%
\begin{alabsubtext}{Claim}{2.4.1}{}
\(e=(i,j)\in F\logicequiv e\in E
  \mbox{ and }i\mbox{ is not connected to }j\mbox{ in }G_e\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Claim}{2.4.1}{}
\prooffontshape
%
  Let \(e=(i,j)\in E\)\@. Denote by \(F_e\) the forest which the
  greedy algorithm built at the time it was checking \(e\)\@. So
  \(e\in F\) if and only if \(e\) does not close a cycle in \(F_e\)\@.
%
\paragraph{(\(\logicimplies\))}
\(e \in F\) and therefore, \(e\) does not close a cycle in \(F_e\),
but then \(e\) does not close a cycle in the transitive closure of
\(F_e\), and in particular \(e\) does not close a cycle in \(G_e\)\@.
%
\paragraph{(\(\logicimplied\))}
\(e\) does not close a cycle in \(G_e\) therefore, \(e\) does not
close a cycle in \(F_e\) and \(e \in F\)\@.
%
{\samepage\markendlst{Proof of Claim 2.4.1}}
\end{alabsubtext}
%
Therefore, \(\function{SF}_{i,j}(G)=\logicnot x_{i,j}\) or \(i\) is
connected to \(j\) in \(G_{(i,j)}\)\@. Because \(\logicnot x_{i,j}\) can be
viewed as the connectivity problem over the graph with two vertices
and one edge labeled \(\logicnot x_{i,j}\), it follows from
lemmas~2.1 and~2.3 that \(\function{SF}\) reduces to
\(\complexityclass{USTCON}\)\@. Notice, however, that the reduction is
not monotone\@.
%
{\samepage\markendlst{Proof of Lemma 2.4}}
\end{alabsubtext}
%
\asubsection{2.4}{Putting it together}
%
\apar{2.4-1}
First, we want to build a function that takes one representative from
each connected component\@. We define \(\function{LI}_i(G)\) to be
\(0\) if and only if the vertex \(i\) has the largest index in its
connected component\@.
%
\begin{alabsubtext}{Definition}{2.4}{}
%
\(\function{LI}(G)\in\{0,1\}^n\)
%
\[
\function{LI}_i(G)=
  \condval{%
    0 & \mbox{\(i\) has the largest index in its connected component}\\
    1 & \mbox{otherwise}
  }
\]
%
\sentence
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{2.5}{}
\(\function{LI}\) reduces to \(\complexityclass{USTCON}(\functionclass{poly})\)\@.
\sentence
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.5}{}
\prooffontshape
%
  \(\function{LI}_i(G)=
  \logiciteror_{j=i+1}^n(i\mbox{ is connected to }j\mbox{ in }G)\)\@.
%
  So \(\function{LI}\) is a simple monotone formula over connectivity
  problems, and \(\function{LI}\) reduces to
  \(\complexityclass{USTCON}\) by lemmas~2.1 and~2.3\@. This is,
  actually, a monotone reduction\@.
%
{\samepage\markendlst{Proof of Lemma 2.5}}
\end{alabsubtext}
%
\apar{2.4-2}
Using the spanning forest and the \(\function{LI}\) function, we can
exactly compute the number of connected components of~\(G\) (i.e.,
given \(G\), we can compute a function \(\function{NCC}_i\) which is
\(1\) iff there are exactly \(i\) connected components in~\(G\))\@.
%
\begin{alabsubtext}{Definition}{2.5}{}
\(\function{NCC}(G)\in\{0,1\}^n\)
%
\[
\function{NCC}_i(G)=
  \condval{%
    1 & \mbox{there are exactly \(i\) connected components in \(G\)} \\
    0 & \mbox{otherwise}
  }
\]
%
\sentence
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{2.6}{}
  \(\function{NCC}\) reduces to
  \(\complexityclass{USTCON}(\functionclass{poly})\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.6}{}
\prooffontshape
%
  Let \(F\) be a spanning forest of \(G\)\@.  It is easy to see that
  if \(G\) has \(k\) connected components, then \(\setsize{F}=n-k\)\@.
%
  Define:
%
\begin{eqnarray*}
  f(G) & = & \function{Sort}\circ\function{LI}(G) \\
  g(G) & = & \function{Sort}\circ\function{SF}(G)
\end{eqnarray*}
\sentence
%
  Then:
%
\[
\begin{array}{rclcl}
  f_i(G)=1 & \logicimplies & k<i \\
  g_i(G)=1 & \logicimplies & n-k<i & \logicimplies & k>n-i,
\end{array}
\]
and thus:
\[
  \function{NCC}_i(G)=f_{i+1}(G)\logicand g_{n-i+1}(G)
\]
\sentence
%
Therefore, applying lemmas~2.1, 2.2, 2.3, 2.4, and~2.5 proves the lemma\@.
%
{\samepage\markendlst{Proof of Lemma 2.6}}
\end{alabsubtext}
%
\apar{2.4-3}
Finally, we can reduce the non-connectivity problem to the connectivity
problem, thus proving that \(\complexityclass{SL}=co\complexityclass{SL}\)\@.
%
\begin{alabsubtext}{Lemma}{2.7}{}
  \(co\complexityclass{USTCON}\) reduces to
  \(\complexityclass{USTCON}(\functionclass{poly})\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2.7}{}
\prooffontshape
%
  Given \((G,s,t)\), define \(G^+\) to be the graph \(G \cup
  \{(s,t)\}\)\@. Denote by \(\function{\#CC}(H)\) the number of
  connected components in the undirected graph \(H\)\@.
%
\begin{eqnarray*}
s\mbox{ is not connected to }t\mbox{ in }G & \logicequiv
   & \function{\#CC}(G^+)=\function{\#CC}(G)-1 \\ 
 & \logicequiv
   & \logiciteror_{i=2}^{n}\function{NCC}_i(G)\logicand
    \function{NCC}_{i-1}(G^+)
\end{eqnarray*}
\sentence
%
  Therefore, applying lemmas~2.1, 2.3, and~2.6 proves the lemma\@.
%
{\samepage\markendlst{Proof of Lemma 2.7}}
\end{alabsubtext}
%
\asection{3}{Extensions}
%
\apar{3-1}
Denote by \(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}\)
the class of languages accepted by \(\complexityclass{Logspace}\)
oracle Turing machines with an oracle from \(\complexityclass{SL}\)\@.
An oracle Turing machine has a work tape and a write-only query tape
(with unlimited length) which is initialized after every query\@. We
get:
%
\begin{alabsubtext}{Corollary}{3.1}{}
  \(~\complexityclass{L}^{\langle\complexityclass{SL}\rangle}=
  \complexityclass{SL}\)\@.
\end{alabsubtext}
\sentence
%
\begin{alabsubtext}{Proof of Corollary}{3.1}{}
\prooffontshape
%
\apar{Corollary 3.1 Proof-1}
  Let \(M\) be an oracle Turing Machine running in
  \(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}\),
  and fix an input \(\vec{x}\) to \(M\)\@.
%
  We build the ``configuration'' graph \(G(V,E)\) of \(M\) using the
  following process:
\begin{itemize}
\item Let \(V\) contain all possible configurations\@.
\item Then, \((v,w) \in E\) with the label ``\(q\) is (not)
  \(s\)--\(t\) connected,'' if, starting from configuration \(v\), the
  next query is \(q\)\@. If the oracle answers that ``\(q\) is (not)
  connected,'' then the machine moves to configuration \(w\)\@.
\end{itemize}
\sentence
%
\apar{Corollary 3.1 Proof-2}
  Notice that we can ignore the direction of the edges, as backward
  edges do not benefit us\@. The reason is that from any vertex \(v\)
  there is only one forward edge leaving \(v\) that can be traversed
  (i.e., whose label matches the oracle's answer)\@. Therefore, if we
  reach \(v\) using a ``backward edge'' \(\graphedge{w}{v}\), then the
  only forward edge leaving \(v\) that can be traversed is
  \(\graphedge{v}{w}\)\@. \apar{Corollary 3.1 Proof-3} Now we can
  replace query edges labeled ``\(q\) is connected'' with the
  \(s\)--\(t\) connectivity problem \(q\), and edges labeled ``\(q\) is
  not connected'' with the \(s\)--\(t\) connectivity problem obtained
  using our theorem that
  \(\complexityclass{SL}=co\complexityclass{SL}\), resulting in one, not
  too big, \(s\)--\(t\) connectivity problem\@. It is also clear that
  this can be done in \(\complexityclass{Logspace}\), completing the
  proof\@.
%
{\samepage\markendlst{Proof of Corollary 3.1}}
\end{alabsubtext}
%
\apar{3-2}
As the symmetric \(\complexityclass{Logspace}\) hierarchy defined
in \cite{cj95-01-13} is known to be within
\(\complexityclass{L}^{\langle\complexityclass{SL}\rangle}\), this
hierarchy collapses to \(\complexityclass{SL}\)\@.
%
\apar{3-3}
As can be easily seen, the above argument holds for any undirected
graph with undirected query edges, which is exactly the definition of
\(\complexityclass{SL}^{\langle\complexityclass{SL}\rangle}\) given
by \cite{cj95-01-3}\@. Thus,
\(\complexityclass{SL}^{\langle\complexityclass{SL}\rangle}=
\complexityclass{SL}\), and, by induction, the
\(\complexityclass{SL}\) hierarchy defined in \cite{cj95-01-3} collapses
to \(\complexityclass{SL}\)\@.
%
\asection{4}{Acknowledgments}
\apar{4-1}
We would like to thank Amos Beimel, Allan Borodin, Assaf Schuster,
Robert Szelepcs\'enyi, and Avi Wigderson for helpful discussions\@.
%
\end{articletext}
%
\begin{articlebib}
%
\bibliographystyle{\the\rbibstyle}
\bibliography{cj95-01}
%
\end{articlebib}
%
\end{document}