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