% The Chicago Journal of Theoretical Computer Science, Volume 1996, Article 2
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1996 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.
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\ifx\nopagebreakendpar\undeftex
  \newcommand{\nopagebreakendpar}{\@endparpenalty10000}
\fi
\catcode`\@=12
%
\newcommand{\textuprm}[1]{\textup{\textrm{#1}}}
%
\mathstyleclass{\complexityclass}{\mathord}{\textuprm}
\mathstyleclass{\problemset}{\mathord}{\textuprm}
\mathstyleclass{\IDtag}{\mathord}{\textit}
%
\newcommand{\setofset}[1]{\mathcal{#1}}
\newcommand{\orderof}[1]{O(#1)}
%
\newcommand{\strlength}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\numofpaths}[1]{\mu(#1)}
\newcommand{\setsymdiff}{\mathop{\triangle}}
\newcommand{\setdiff}{-}
%
\newcommand{\parity}{\oplus}
\newcommand{\iterparity}{\bigoplus}
\newcommand{\circand}{\wedge}
\newcommand{\circor}{\vee}
\newcommand{\circnot}{\neg}
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textrm}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\mathcal}[1]{{\cal #1\/}}\fi
%
\newcommand\nohyphenl[1]{{\discretionary{}{}{}{#1}}}
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{{\ooalign
    {\hfil\raise.07ex\hbox{{\scriptsize\textup{R}}}\hfil\crcr\mathhexbox20D}}}
%
% Macros for the editors' comment
%
% The cross symbol indicates a recently deceased editor.
%
\ifx\deceased\undeftex
  \newcommand{\deceased}[1]{\dag#1}
\fi
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1996, Article 2\\
      \textit{27 March 1996}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142 USA; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://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
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert\registered,
  SciSearch\registered, Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\registered.}
}
%
\copyrightstmt{%
  \copyright 1996 The 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 & \deceased{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}
    \vspace{1ex}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1996}
%
\articleid{2}
%
\selfcitation{
     @article{cj96-02,
       author={Mitsunori Ogihara},
       title={Sparse Hard Sets for P Yield Space-Efficient Algorithms},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1996},
       number={2},
       publisher={MIT Press},
       month={March},
       year={1996}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Sparse Hard Sets for P Yield Space-Efficient Algorithms}
\shorttitle{Sparse Hard Sets}
\collectiontitle{}
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Mitsunori Ogihara}
   \collname{}{Ogihara, Mitsunori}
   \begin{institutioninfo}
       \instname{University of Rochester}
       \department{Department of Computer Science}
       \address{}{Rochester}{NY}{USA}{14627}
   \end{institutioninfo}
   \email{ogihara@cs.rochester.edu}
\end{authorinfo}
%
\shortauthors{Ogihara}
%
\begin{editinfo}
  \submitted{14}{3}{1995}\reported{6}{1}{1996}
  \submitted{15}{1}{1996}\reported{28}{2}{1996}
  \submitted{29}{2}{1996}\reported{1}{3}{1996}\published{27}{3}{1996}
\end{editinfo}
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
%
\apar{Abstract-1}
In 1978, Hartmanis conjectured that there exist no sparse complete
sets for \(\complexityclass{P}\) under logspace many-one reductions\@.
In this paper, in support of the conjecture, it is shown that if
\(\complexityclass{P}\) has sparse hard sets under logspace many-one
reductions, then
\(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\)\@.
%
\end{abstract}
%
\asection{1}{Introduction}
{\sloppy
%
\apar{1-1}
In 1978, Hartmanis~\cite{cj96-02-07} conjectured that no
\(\complexityclass{P}\)-complete sets under logspace many-one
reductions can be polynomially sparse; i.e., for any set
\(A\in\complexityclass{P}\) to which every set in
\(\complexityclass{P}\) is logspace many-one reducible, the function
that maps \(n\) to the number of elements in \(A\) of length up to
\(n\) is not bounded by a polynomial in \(n\)\@. The conjecture is
interesting and fascinating\@. If the conjecture is true, then
\(\complexityclass{L}\neq\complexityclass{P}\), because
\(\complexityclass{L}=\complexityclass{P}\) implies that every
nonempty finite set is \(\complexityclass{P}\)-complete\@. So, since it
is widely assumed that \(\complexityclass{L}\) is different from
\(\complexityclass{P}\), one might believe the validity of the
conjecture\@. Such reasoning may well be fallacious: proving this
conjecture is \emph{at least} as hard as proving
\(\complexityclass{L}\neq\complexityclass{P}\), and therefore, it may
well be the case that even though
\(\complexityclass{L}\neq\complexityclass{P}\),
\(\complexityclass{P}\) has polynomially sparse complete sets\@. In
order to support the conjecture, one would perhaps need to show a
result in the other direction; that is, if the conjecture \emph{does
not} hold, then some ``implausible'' event occurs\@. Such an
implausible event would be the collapse of \(\complexityclass{P}\) to
a (presumably) much smaller class\@. As sets in \(\complexityclass{P}\)
already have time-efficient recognition algorithms, this should mean
that \(\complexityclass{P}\) has space-efficient algorithms, e.g.,
\(\complexityclass{P}\) is included in
\(\complexityclass{DSPACE}[\log^k n]\) for some \(k\)\@.
%
\apar{1-2}
}
The conjecture is reminiscent of the celebrated Berman-Hartmanis
conjecture~\cite{cj96-02-02} that all
\(\complexityclass{NP}\)-complete sets under polynomial-time many-one
reduction are polynomially isomorphic\@. If the Berman-Hartmanis
conjecture is true, then
\(\complexityclass{P}\neq\complexityclass{NP}\) and polynomially
sparse sets cannot be \(\complexityclass{NP}\)-complete\@. A result to
support this conjecture was obtained by Mahaney~\cite{cj96-02-10}\@. He
showed that if there is a polynomially sparse hard set for
\(\complexityclass{NP}\), then
\(\complexityclass{P}=\complexityclass{NP}\); that is, unless
\(\complexityclass{NP}\) collapses to the seemingly small class
\(\complexityclass{P}\), \(\complexityclass{NP}\) cannot have sparse
complete sets\@.
%
\apar{1-3}
In contrast with the sparse hard set problem for
\(\complexityclass{NP}\), not much work has been done on the
Hartmanis conjecture for \(\complexityclass{P}\)---we could call it
``the sparse hard set problem for \(\complexityclass{P}\)\@.'' The only
paper I am aware of is by Hemaspaandra, Ogihara, and
Toda~\cite{cj96-02-08}, who prove that \(\complexityclass{P}\) cannot
have \emph{poly-logarithmic} sparse hard sets unless
\(\complexityclass{P}\) is included in \(\complexityclass{SC}\), the
class of sets recognized simultaneously in polynomial-time and in
poly-logarithmic space\@. As one can easily see, the result is still
too weak because the poly-logarithmic sparsity is a much more
stringent condition than polynomial sparsity\@.
%
\apar{1-4}
In this paper, I give the first solution to the sparse hard set
problem for \(\complexityclass{P}\) by showing that unless
\(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\),
the Hartmanis conjecture holds for \(\complexityclass{P}\)\@.
%
\begin{alabsubtext}{Theorem}{1}{}
  There exist no sparse \(\complexityclass{P}\)-hard sets under
  logspace many-one \nohyphenl{reductions} unless
  \(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\)\@.
\end{alabsubtext}
%
\apar{1-5}
Let us say a few words about the proof\@. Assuming the existence of a
sparse \(\complexityclass{P}\)-hard set, we are able to reduce, in a
space-efficient manner, any instance of the circuit value problem to
\(\problemset{Parity-CVP}\), the circuit value problem of a circuit
consisting exclusively of parity gates\@. However, this restricted
circuit value problem is known to be in
\(\complexityclass{DSPACE}[\log^2 n]\)\@.
%
\apar{1-6}
Readers familiar with the class
\(\complexityclass{\(\parity\)L}\)~\cite{cj96-02-03}, a logarithmic
space-bounded version of \(\complexityclass{\(\parity\)P}\)
{}~\cite{cj96-02-11,cj96-02-06}, will recognize our reduction to map
an instance of the circuit value problem to a problem in
\(\complexityclass{\(\parity\)L}\), and recall that
\(\complexityclass{\(\parity\)L}\subseteq
\complexityclass{DSPACE}[\log^2 n]\)
(see~\cite{cj96-02-03} and ~\cite{cj96-02-01})\@.
%
\apar{1-7}
The paper is organized as follows\@. In Section~2, I define the basic
notation and the circuit value problems\@. In Section~3, I prove the
main theorem\@.
%
\asection{2}{Circuit Value Problems}
%
\apar{2-1}
A Boolean circuit is a directed acyclic graph \(C\) with labeled
nodes\@. Nodes in \(C\) with indegree \(0\) are called \emph{input
gates}, while the other gates are called \emph{interior gates}\@. Input
gates in \(C\) have distinct labels from \(\{1,\ldots,n\}\), where
\(n\) is the number of input gates in \(C\)\@. There is one designated
node in \(C\) with outdegree \(0\), which is called the \emph{output
gate}\@. Each interior gate is labeled by a Boolean function chosen from
\(\{\circnot,\circand,\circor\}\)\@. A gate labeled by \(\circnot\) is
called a \emph{NOT} gate and has indegree \(1\)\@. A gate labeled by
\(\circand\) (or \(\circor\)) is called an \emph{AND} gate (an \emph{OR}
gate, respectively) and has indegree \(\geq 2\)\@. A gate \(g\) is said
to be a \emph{direct input} to a gate \(g'\) if there is an arc from
\(g\) to \(g'\) in \(C\)\@.
%
\apar{2-2}
A Boolean circuit is said to be of \emph{bounded fan-in} if every gate
has indegree \(\leq 2\)\@. It is said to be of \emph{unbounded fan-in}
if some gate may have indegree \(> 2\)\@. A Boolean circuit is encoded
by its adjacency matrix and the labels of the gates, where I always
assume that the output gate is the last node and for every \(i\), the
\(i\)-th input gate is the \(i\)-th node\@.
%
\apar{2-3}
Let \(C\) be a Boolean circuit of \(m\) gates and \(n\) inputs and
let \(x=x_1\cdots x_n\in\{0,1\}^n\)\@. For each \(i\), \(1\leq i\leq m\),
let \(g_i\) denote the \(i\)-th gate in \(C\)\@. For \(i\), \(1\leq i\leq m\),
the output of \(g_i\) in \(C\) on input \(x\), denoted by
\(C[x,i]\), is determined inductively as follows\@:
%
\begin{itemize}
\item If \(g_i\) is an input gate labeled by \(j\), then \(C[x,i]=x_j\)\@.
\item If \(g_i\) is a NOT gate whose unique direct input is \(g_j\),
  then \(C[x,i]=\circnot(C[x,j])\)\@.
\item If \(g_i\) is an AND gate and its direct inputs are
  \(g_{j_1},\ldots,g_{j_k}\), then \(C[x,i]=C[x,j_1]
  \circand\cdots\circand C[x,j_k]\)\@.
\item If \(g_i\) is an OR gate and its direct inputs are
  \(g_{j_1},\ldots,g_{j_k}\), then
  \(C[x,i]=C[x,j_1]\circor\cdots\circor C[x,j_k]\)\@.
\end{itemize}
%
The output of \(C\) on input \(x\), denoted by \(C(x)\), is \(C[x,m]\)\@.
%
\apar{2-4}
The circuit value problem (\(\problemset{CVP}\)) is the problem of
deciding whether a bounded fan-in Boolean circuit \(C\) outputs \(1\)
on input \(x\)\@. Ladner~\cite{cj96-02-09} showed that
\(\problemset{CVP}\) is complete for \(\complexityclass{P}\) under
logspace many-one reductions\@. A circuit \(C\) is \emph{topologically
sorted} if for every \(i,j\), if \(g_i\) is a direct input gate of
\(g_j\), then \(i<j\)\@. One can easily observe that the construction
by Ladner can be used to show that the topologically sorted version of
the problem, \(\problemset{TSCVP}\), is complete under logspace
many-one reductions\@. I will identify \(\problemset{TSCVP}\) with the
set of all strings \(C\#x\) such that \(C\) is a topologically sorted
Boolean circuit of \(n\) inputs, \(\strlength{x}=n\), and \(C(x)=1\)\@.
%
\apar{2-5}
The parity function, denoted by \(\parity\), maps a binary string to
the parity of the number of \(1\)s in it\@. I also view \(\parity\)
as the function that maps a natural number \(n\) to (\(n\) modulo
\(2\))\@. A parity (or, exclusive-or) gate is a gate of unbounded
fan-in that, given binary bits \(a_1,\ldots,a_n\) as inputs, computes
\(\parity(a_1\cdots a_n)\)\@. By convention, I will use both
\(\parity(a_1,\cdots,a_n)\) and \(a_1\parity\cdots\parity a_n\) to
denote \(\parity(a_1\cdots a_n)\)\@. A parity circuit is an unbounded
fan-in circuit in which all the gates compute \(\parity\)\@. The
\emph{parity circuit problem} is defined as a variation of the circuit
value problem, in which it is asked whether a parity circuit outputs
\(1\) on a specified input\@. I define \(\problemset{Parity-CVP}\)
to be the set corresponding to the problem: The set of all \(C\#x\)
such that \(C\) is a parity circuit and, on input \(x\), outputs
\(1\)\@.
%
\apar{2-6}
A set \(L\) is in \(\complexityclass{\(\parity\)L}\)~\cite{cj96-02-03}
if there exists a logarithmic space-bounded nondeterministic Turing
machine \(N\) such that for every \(x\), \(x\in L\) if and only if the
number of accepting computation paths of \(N\) on \(x\) is odd\@.
%
\begin{alabsubtext}{Proposition}{2}{}
  \(\problemset{Parity-CVP}\) is in \(\complexityclass{\(\parity\)L}\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Proposition}{2}{}
\prooffontshape
%
\apar{Proof of Prop 2-1}
Let \(C\) be a parity circuit of \(m\) gates \(g_1,\ldots,g_m\) and
\(n\) input gates, and let \(x=x_1\cdots x_n\)\@. Note for any
\(a,b,c\in\{0,1\}\), that
\(\parity(a,b,c)=\parity(\parity(a,b),c)=\parity(a,\parity(b,c))\)\@.
%
\apar{Proof of Prop 2-2}
For each \(i\), \(1\leq i\leq m\), let \(\numofpaths{i}\) denote the
number of paths in \(C\) on \(x\) from some input gate with value
\(1\) to the gate \(g_i\)\@. I claim for any \(i\), \(1\leq i\leq m\),
that \(C[x,i]=\parity(\numofpaths{i})\)\@. This is proven by induction\@.
%
\apar{Proof of Prop 2-3}
For the base case, let \(g_i\) be an input gate\@. Then \(C[x,i]=1\) if
and only if \(x_i=1\)\@. Trivially, there is exactly one path from the
gate to itself\@. So, the claim holds\@.
%
\apar{Proof of Prop 2-4}
For the induction step, let \(g_i\) be an interior gate and let
\(g_{h_1},\ldots,g_{h_l}\) be an enumeration of all direct inputs to
\(g_i\)\@. Clearly, \(\numofpaths{i}=\sum_{j=1}^l\numofpaths{h_j}\)\@.
Suppose that the claim holds for \(h_1,\ldots,h_l\), i.e.,
\(C[x,h_j]=\parity(\numofpaths{h_j})\) for all \(j,1\leq j\leq l\)\@.
By definition, \(C[x,i]=\parity(C[x,h_1]+\cdots+C[x,h_l])\)\@. So,
\[C[x,i]=\iterparity_{j=1}^l(\parity(\numofpaths{h_j}))=
\iterparity_{j=1}^l(\numofpaths{h_j})=\parity(\numofpaths{i})\]\sentence
Thus, the claim holds for \(g_i\)\@. Hence the claim holds for every
gate\@.
%
\apar{Proof of Prop 2-5}
Now, noting that Boolean circuits are acyclic, it is easy to construct
a nondeterministic machine witnessing
\(\problemset{Parity-CVP}\in\complexityclass{\(\parity\)L}\)\@. Our
machine, on input \(C\#x\), guesses a sequence
\(g_{i_1},\ldots,g_{i_h}\) of at most \(m\) gates, and accepts if and
only if the sequence is a path from an input gate outputting \(1\) to
the output gate\@. The verification can be done sequentially, so the
machine has only to store two consecutive elements in the sequence\@.
So, it can be logarithmic space-bounded\@. Clearly, the number of
accepting computation paths of the machine on \(C\#x\) is equal to the
number of paths in \(C\) on \(x\) from some input gate with value
\(1\) to the output gate\@. So, the machine witnesses that
\(\problemset{Parity-CVP}\in\complexityclass{\(\parity\)L}\)\@. This
proves the proposition\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Proposition 2}}
\end{alabsubtext}
%
{\nopagebreakendpar
\begin{alabsubtext}{Proposition}{3}{\protect\cite{cj96-02-03,cj96-02-01}}
  \(\complexityclass{\(\parity\)L}\subseteq
    \complexityclass{DSPACE}[\log^2 n]\)\@.
\end{alabsubtext}
%
Here I provide a sketch of the proof, which is reminiscent of
Savitch's \nohyphenl{theorem}~\cite{cj96-02-12}\@.
}
%
\begin{alabsubtext}{Proof of Proposition}{3}{}
\prooffontshape
%
Let \(N\) be a logarithmic space-bounded nondeterministic machine
\(N\) witnessing that \(L\in\complexityclass{\(\parity\)L}\), and let
\(x\) be an input to \(N\)\@. For two IDs \(I\) and \(J\) of \(N\) on
\(x\) and a natural number \(t\), define \(Q(I,J,t)\) to be the parity
of the number of computation paths of \(N\) on \(x\) from \(I\) to
\(J\) of length at most \(2^t\)\@. Define \(Q(I,I,t)=1\) for every
\(I\) and \(t\)\@. Let \(m=\orderof{\log\strlength{x}}\) be a natural
number such that \(N\) on \(x\) runs for at most \(2^m\) steps, and
let \(I_{\IDtag{ini}}\) be the unique start ID of \(N\) on \(x\)\@. We
may assume that there is a unique accepting ID of \(N\) on
\(x\)\@. Let \(I_{\IDtag{acc}}\) denote this ID\@. Clearly, \(x\in L\)
if and only if \(Q(I_{\IDtag{ini}},I_{\IDtag{acc}},m)=1\)\@. Note for
every \(I\), \(J\), and \(t>0\), that
\[Q(I,J,t)=\iterparity_K(Q(I,K,t-1)Q(K,J,t-1))\]
where \(K\) ranges over all IDs of \(N\) on \(x\)\@. This suggests the
following recursive procedure to evaluate \(Q(I,J,t)\)\@:
%
{\sloppy
\begin{itemize}
\item If \(I=J\), then return \(1\)\@.
\item If \(I\neq J\) and \(t=0\), then compute and return \(Q(I,J,0)\) by
  simulating one move of \(N\) on \(x\) at ID \(I\)\@.
\item If \(I\neq J\) and \(t>0\), then set \(c\) to \(0\) and for each \(K\),
  set \(c\) to {\binoppenalty=10000\((c+Q(I,K,t-1)Q(K,J,t-1))\)}
  modulo \(2\)\@.
\end{itemize}
%
If we run this procedure to evaluate
\(Q(I_{\IDtag{ini}},I_{\IDtag{acc}},m)\), then the recursion depth is
\(m=\orderof{\log\strlength{x}}\)\@. Since each ID is encoded as a
string of length \(\orderof{\log\strlength{x}}\), the evaluation
requires \(\orderof{\log^2 \strlength{x}}\) space, and thus,
\(L\in\complexityclass{DSPACE}[\log^2 n]\)\@.
}
%
{\nopagebreakbeginpar\markendlst{Proof of Proposition 3}}
\end{alabsubtext}
%
\apar{2-7}
From the above two propositions, I immediately obtain the
following:
%
\begin{alabsubtext}{Proposition}{4}{}
  \(\problemset{Parity-CVP}\in\complexityclass{DSPACE}[\log^2 n]\)\@.
\end{alabsubtext}
%
\asection{3}{Proof of Theorem~1}
%
\apar{3-1}
I repeat the statement of the theorem\@.
\begin{alabsubtext}{Theorem}{1}{}
  There exist no sparse \(\complexityclass{P}\)-hard sets under
  logspace many-one \nohyphenl{reductions} unless
  \(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
%
\apar{Proof of Theorem 1-1}     
Suppose that there exists a sparse \(\complexityclass{P}\)-hard set
under logspace many-one reductions\@. Then I show that
\(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\),
in particular, \(\problemset{TSCVP}\) is in
\(\complexityclass{DSPACE}[\log^2 n]\)\@.
%
\apar{Proof of Theorem 1-2}
I will make use of the following set \(A\): \(A\) is the set of all
strings of the form \(C\#x\#I\#b\) such that:
%
\begin{itemize}
\item \(C\#x\) is an instance of \(\problemset{TSCVP}\), i.e., \(C\)
  is a topologically
  sorted Boolean circuit with \(m\) gates and \(n\) inputs and
  \(x\in\{0,1\}^n\),
\item \(I\) is a nonempty subset of \(\{ 1,\ldots,m\}\) encoded as
  the enumeration of its elements in increasing order,
\item \(b\in\{0,1\}\), and
\item \(\iterparity_{i\in I}C[x,i]=b\)\@.
\end{itemize}
%
Clearly, \(A\in\complexityclass{P}\)\@. So, by our supposition, \(A\)
is logspace many-one reducible to a sparse set \(S\) via some function
\(f\)\@. Note that for a sufficiently large \(m\) and every legitimate
\(C\#x\#I\#b\), it holds that \(\strlength{C\#x\#I\#b}\leq
2\strlength{C\#x}\)\@. Since \(S\) is sparse, this implies that for
every \(C\#x\), the number of \(y\in S\) such that \(y=f(C\#x\#I\#b)\)
for some \(I\) and \(b\) is bounded by \(2^{d\log\strlength{C\#x}}\)
for some \nohyphenl{constant}~\(d\)\@.
%
\apar{Proof of Theorem 1-3}
Let \(C\#x\) be fixed, whose membership in \(\problemset{TSCVP}\) we
are testing\@. Let \(g_1,\ldots,g_m\) be the gates of \(C\), where
\(g_1,\ldots,g_n\) are the input gates and \(g_m\) is the output gate\@.
Let \(l=\strlength{C\#x}\) and \(e=\lceil d\log l\rceil\)\@. As we have
already fixed \(C\) and \(x\), I will simply use \(I\#b\) to denote
\(C\#x\#I\#b\) by dropping \(C\) and \(x\)\@. By the above observation,
the number of \(y\in S\) such that \(y=f(I\#b)\) for some
\(I\in\{1,\ldots,m\}\) and \(b\in\{0,1\}\) is less than \(2^e\)\@.
%
\apar{Proof of Theorem 1-4}
Now I introduce the notion of \emph{good} gates and \emph{bad} gates\@.
Let \(\setofset{T}\) be the set of all nonempty subsets of
\(\{1,\ldots,m\}\) of size at most \(e\)\@. Let
\(i\in\{n+1,\ldots,m\}\)\@. I say that \(g_i\) is good if there exist
distinct \(I,J\in\setofset{T}\) and \(b,c\in\{0,1\}\) such that
%
\[f(I\#b)=f(J\#c)\mbox{ and }i=\max(I\setsymdiff J)\]
%
where \(I\setsymdiff J\) denotes the symmetric difference of \(I\) and
\(J\)\@. Otherwise, \(g_i\) is called bad\@. Intuitively, an interior
gate \(g_i\) is good if we can easily find a set of gates
\(g_j,\ldots,g_k\) such that the parity of the output of these gates
is equal to the output of \(g_i\), and thus, the evaluation of \(g_i\)
can be reduced to the evaluation of \(g_j,\ldots,g_k\)\@.
%
\apar{Proof of Theorem 1-5}
The outline of the main steps of the proof is as follows: (1) show
that there are very few bad gates; (2) construct a parity circuit
\(D\) whose inputs are \(x\) and the bad gates, and whose interior
gates are good gates; (3) show that for some assignment of values
to the bad gates in \(D\), the value of each gate in \(D\) is equal to
the value of the corresponding gate in \(C\); and (4) use the fact that
\(D\) can be computed in polylog space\@.
%
{\nopagebreakendpar
\apar{Proof of Theorem 1-6}
%
\begin{alabsubtext}{Claim}{1}{}
  The number of bad gates is at most \(e\)\@.
\end{alabsubtext}
}
%
\begin{alabsubtext}{Proof of Claim}{1}{}
\prooffontshape
%
Assume that there are \(e+1\) bad gates and let
\(g_{h_1},\ldots,g_{h_{e+1}}\) be an enumeration of \(e+1\) bad gates\@.
Let \(\setofset{R}\) be the set of all nonempty subsets of
\(\{h_1,\ldots,h_{e+1}\}\) of size at most \(e\)\@. Note for any
\(I\in\setofset{R}\), that exactly one of \(f(I\#0)\) or \(f(I\#1)\)
is in \(S\), because exactly one of \(I\#0\) or \(I\#1\) is in \(A\)\@.
So, let \(b_I\) be the unique \(b\in\{0,1\}\) such that \(f(I\#b) \in
S\)\@. Note also, for any distinct \(I,J\in\setofset{R}\), that
\(f(I\#b_I)\neq f(J\#b_J)\)\@. Otherwise, \(g_k\) with
\(k=max(I\setsymdiff J)\), which is bad by our assumption, is good, a
contradiction\@. Since there are \(2^{e+1}-2\geq 2^e\) elements in
\(\setofset{R}\), we can collect \(2^e\) elements in \(S\), which
contradicts the assumption that there are less than \(2^e\) elements
in \(S\) we see as the image of \(f\)\@. This proves the claim\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Claim 1}}
\end{alabsubtext}
%
\apar{Proof of Theorem 1-7}
Now let \(g_{h_1},\ldots,g_{h_q}\) be the enumeration of all bad gates
and let \(H=\{h_1,\ldots,h_q\}\), where \(q\leq e\)\@. For each good
\(g_i\), let \((I(i),b(i),J(i),c(i))\) be the lexicographically
minimum \((I\#b,J\#b)\) witnessing that \(g_i\) is good\@. I define a
parity circuit \(D\) with \(m+1\) gates and \(n+q+1\) input gates as
follows\@:
%
\begin{itemize}
\item The gates of \(D\) are those of \(C\) plus one new gate \(g_0\)\@.
\item The input gates of \(D\) are \(g_0\), the input gates of \(C\),
  and the bad gates; that is, they are
  \(g_0,g_1,\ldots,g_n,g_{h_1},\ldots,g_{h_q}\)\@.
  I will fix the input to \(g_0\) to \(1\)\@.
\item Each interior gate \(g_i\) in \(D\) computes the parity
  function, whose direct inputs are given as follows\@:
%
  \begin{itemize}
  \item If \(b(i)=c(i)\), then all \(g_j\) with
    \(j\in(I(i)\setsymdiff J(i))\setdiff\{i\}\)\@.
  \item If \(b(i)\neq c(i)\), then all \(g_j\) with
    \(j\in(I(i)\setsymdiff J(i))\setdiff\{i\}\) plus \(g_0\)\@.
  \end{itemize}
%
\end{itemize}
%
Note that \(D\) is topologically sorted since \(C\) is topologically
sorted, and if \(g_i\) is good then \(i\) is the largest in
\(I(i)\setsymdiff J(i)\)\@.
%
\apar{Proof of Theorem 1-8} 
I say that \(v\in\{0,1\}^q\) is valid if the value assigned by \(v\)
to each bad gate is equal to the value of the bad gate in \(C\#x\);
i.e., for all \(t,1\leq t\leq q\), the \(t\)-th bit of \(v\) is equal
to \(C[x,h_t]\)\@. It is obvious that there is a unique valid \(v\)\@.
%
{\nopagebreakendpar
\begin{alabsubtext}{Claim}{2}{}
  \(v\) is valid if and only if for every gate \(g_i,i,1\leq i\leq m\),
  \(C[x,i]=D[1xv,i]\)\@.
\end{alabsubtext}
}
%
{\nopagebreakbeginpar
\begin{alabsubtext}{Proof of Claim}{2}{}
\prooffontshape
%
The implication from right to left is obvious\@. The other direction is
proven inductively\@. First, note that \(C[x,i]=D[1xv,i]\) holds for
every bad gate \(g_i\)\@. Next, let \(g_i\) be a good gate and suppose
that the claim holds for every direct input \(g_j\) of \(g_i\) in
\(D\)\@. I have \(f(I(i)\#b(i))=f(J(i)\#c(i))\)\@. So,
\[b(i)=\iterparity_{j\in I(i)}C[x,j]\mbox{ if and only if }
c(i)=\iterparity_{j\in J(i)}C[x,j]\]\sentence
This implies
\[C[x,i]=C[x,j_1]\parity\cdots\parity C[x,j_k]\parity b(i)\parity c(i)\]
where \(j_1,\ldots,j_k\) is an enumeration of all \(j\)
such that \(j\neq i\) and \(j\in I(i)\setsymdiff J(i)\)\@.
By our supposition, for each \(t\), \(1\leq t\leq k\),
\(D[1xv,j_t]=C[x,j_t]\)\@. Also, by definition, \(g_0\) is among the
direct inputs of \(g_i\) if and only if \(b(i)\neq c(i)\), i.e.,
\(b(i)\parity c(i)=1\)\@. Thus, \(C[x,i]=D[1xv,i]\)\@.
Hence, the claim holds for \(g_i\)\@. This proves the claim\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Claim 2}}
\end{alabsubtext}
}
%
\apar{Proof of Theorem 1-9}
For each \(v\in\{0,1\}^q\) and \(t\), \(1\leq t\leq q\), I say that
\(v\) is \emph{correct} at \(t\) if, depending on the type of
\(g_{h_t}\) in \(C\), the following conditions are satisfied\@:
%
\begin{itemize}
\item If \(g_{h_t}\) is a NOT gate in \(C\) with \(g_j\) as its direct
  input, then \(v_t\) is equal to \(\circnot(D[1xv,j])\)\@.
\item If \(g_{h_t}\) is an AND gate in \(C\) with \(g_j\) and \(g_k\)
  as its direct inputs, then
  \(v_t\) is equal to \(D[1xv,j]\circand D[1xv,k]\)\@.
\item If \(g_{h_t}\) is an OR gate in \(C\) with \(g_j\) and \(g_k\)
  as its direct inputs, then
  \(v_t\) is equal to \(D[1xv,j]\circor D[1xv,k]\)\@.
\end{itemize}
%
{\nopagebreakendpar
\begin{alabsubtext}{Claim}{3}{}
  \(v\) is valid if and only if for all \(t\), \(1\leq t\leq q\), \(v\)
  is correct at \(t\)\@.
\end{alabsubtext}
}
%
{\nopagebreakbeginpar
\begin{alabsubtext}{Proof of Claim}{3}{}
\prooffontshape
%
The implication from left to right is obvious\@.
To prove the other direction, suppose that \(v\) is not valid\@.
Let \(t\) be the smallest \(i\) such that the \(i\)-th bit of \(v\)
is not equal to the output of the gate of \(C\) on input \(x\);
i.e., \(t\) is the smallest \(i\), \(1\leq i\leq t\), such that
\(v_i=D[1xv,j_i]\neq C[x,j_i]\)\@. Since \(D\) is topologically
sorted, by an argument similar to that in the proof of
Claim~2, we have \(D[1xv,k]=C[x,k]\) for all \(k<j_t\)\@.
If \(v\) is correct at \(t\), then \(v_t\) is equal to \(C[x,j_t]\),
a contradiction\@. So, \(v\) is not correct at \(t\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Claim 3}}
\end{alabsubtext}
}
%
\apar{Proof of Theorem 1-10}
The above claims suggest the following algorithm to reduce \(C\) to
\(D\) with the unique valid \(v\)\@.
%
\begin{description}
\item[Step 1:] For each interior gate of \(C\), test whether it is good, and
  construct \(H\), the set of all bad gates\@.
\item[Step 2:] For each \(v\in\{0,1\}^q\), test whether \(v\) is valid by
  testing whether \(v\) is correct at all \(t\), and if so,
  use the valid \(v\) to compute \(D[1xv,m]\)\@.
\end{description}
%
{\nopagebreakendpar
\begin{alabsubtext}{Claim}{4}{}
  The algorithm can be executed in \(\orderof{\log^2 l}\) space\@.
\end{alabsubtext}
}
%
{\nopagebreakbeginpar
\begin{alabsubtext}{Proof of Claim}{4}{}
\prooffontshape
%
\apar{Proof of Claim 4-1}
Let \(M\) be a logspace machine that computes \(f\)\@. Note that
\(I\in\setofset{T}\) is encoded as a string of length \(\orderof{e\log
m}=\orderof{\log^2 l}\)\@. Given \(I\#b\) and \(J\#c\), test whether
\(f(I\#b)=f(J\#c)\) can be done by simulating \(M\) on \(I\#b\) and
\(M\) on \(J\#c\) simultaneously to compare \(f(I\#b)\) and
\(f(J\#c)\) bit by bit\@. Since \(M\)'s output tape is certainly
write-only, the comparison requires storing only the most recent
output bit from each\@. More precisely, \(M\) on \(I\#b\) and \(M\) on
\(J\#c\) are simulated alternatively step by step\@. If one of the
simulations outputs a new bit of \(f\), then it is suspended until the
other simulation produces a new bit of \(f\) or halts without
outputting a new bit\@. If both produce new bits, then the bits are
compared and, if they are different, it must be the case that the
values of \(f\) are different\@. The comparison is therefore
terminated\@. If only one simulation produces a new bit, then the two
values of \(f\) obviously have different lengths, so the values are
different and the comparison is terminated\@. If both simulations halt
without producing any new bits, then since the bits that have been
produced so far are the same, it must be the case that they have the
same value\@. The amount of space expended by the simulations is
\(\orderof{\log^2 l}\), the amount required to store \(I\#b\) and
\(J\#c\), since \(M\) is logarithmic space-bounded\@.
%
\apar{Proof of Claim 4-2}
To test whether an interior gate \(g_i\) is good, and if so, to
compute \(I(i)\), \(b(i)\), \(J(i)\), and \(c(i)\), it suffices to test,
by cycling through all possible \((I\#b,J\#c)\) in the lexicographic
increasing order, whether \((I\#b,J\#c)\) witnesses that \(g_i\) is
good\@. By the previous discussion, the amount of space required is
\(\orderof{\log^2 l}\)\@. There are at most \(e\) bad gates, so the
amount of space required to store \(H\), the set of all bad gates, is
\(\orderof{e\log m}=\orderof{\log^2 l}\), so, \(H\) can be computed in
space
\(\orderof{\log^2 l}\)\@.
%
\apar{Proof of Claim 4-3}
Note that, as we are developing an \(\orderof{\log^2 n}\) algorithm,
there is not enough space to store the entire description of \(D\)\@.
However, after obtaining \(H\), each bit of the description of \(D\)
is computable in \(\orderof{\log^2 l}\) space as follows: In order to
determine the direct inputs to \(g_i\), if either \(i\leq n\) or
\(i\in H\), then \(g_i\) is an input gate of \(D\), and so, has no
direct inputs; otherwise, \(I(i), b(i), J(i), c(i)\), which are
computable in \(\orderof{\log^2 l}\) space, provide the list of direct
inputs\@.
%
\apar{Proof of Claim 4-4}
To test whether \(v\) is correct at \(t\), since \(h_t\) is the
\(t\)-th element in \(H\) and the type of \(g_{h_t}\) in \(C\) and its
direct input(s) are determined from \(C\#x\), it suffices to compute
\(D[1xv,j]\) for \(j\) such that \(g_j\) is a direct input to
\(g_{h_t}\) in \(C\)\@. Since \(D\) is a parity circuit, the
computation problem is solvable by \(\problemset{Parity-CVP}\)\@.
Recall that I demand that the last gate of a circuit be the output\@.
So, let \(D_j\) be the circuit constructed from \(D\) by making the
connection of \(g_m\) identical to that of \(g_j\)\@. Then
\(D_j(1xv)=D_j[1xv,m]=D[1xv,j]\)\@. Let \(N\) be a deterministic Turing
machine that decides \(\problemset{Parity-CVP}\) in \(\orderof{\log^2
n}\) space\@. Since each bit of the description of \(D\) is computable
in \(\orderof{\log^2 l}\) space, given \(j\), each bit of the
description of \(D_j\) is computable in the same amount of space\@.
Thus, one can simulate \(N\) on \(D_j\#1xv\) by keeping track of the
position of \(N\)'s input head\@. When \(N\) needs to read the \(k\)-th
bit of its input, one has only to activate the algorithm to produce
\(D\) to compute the \(k\)-th bit (by recording the number of bits
produced so far and the current bit), where the bits for the \(m\)-th
gate are computed from those for the \(j\)-th gate\@. Thus,
\(D[1xv,j]\) is computable in \(\orderof{\log^2 l}\) space, and
therefore, whether \(v\) is valid can be tested in the same amount of
space\@.
%
\apar{Proof of Claim 4-5}
Once the valid \(v\) is discovered, since it is of length at most
\(e\), there is enough space to record it\@. Now we have only to
compute \(C[x,m]\) as \(D[1xv,m]\) with the valid \(v\)\@. Again, we
have only to simulate \(N\) while computing the bits of \(D\) on
demand, which requires \(\orderof{\log^2 l}\) space\@. Hence, the whole
process can be done in \(\orderof{\log^2 l}\) space\@. This proves the
claim\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Claim 4}}
\end{alabsubtext}
}
%
This completes the proof of the theorem\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{3-2}
By a straightforward generalization of the proof, I obtain the
following theorem\@.
%
\begin{alabsubtext}{Theorem}{2}{}
  Let \(d,e\geq 1\) and let \(S\) be a set whose density function is
  bounded by \(2^{\orderof{\log^d n}}\)\@. Suppose every set in
  \(\complexityclass{P}\) is many-one reducible to \(S\) via a
  function \(f\) computable in \(\orderof{\log^e n}\) space\@. Then
  \(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^{de+1}n]\)\@.
\end{alabsubtext}
%
\asection{4}{Conclusion}
%
\apar{4-1}
I have given a solution to the Hartmanis conjecture on sparse
complete sets for \(\complexityclass{P}\) by showing that
\(\complexityclass{P}\) cannot have many-one-hard sets of low
density via space-efficient reductions unless
\(\complexityclass{P}\subseteq\complexityclass{DSPACE}[\log^2 n]\)\@.
I note here that, by extending the technique in this paper, Cai and
Sivakumar have recently resolved the conjecture by showing that sparse
\(\complexityclass{P}\)-hard sets exist under logspace many-one
reductions if and only if
\(\complexityclass{P}=\complexityclass{L}\)~\cite{cj96-02-05}\@. The
technique has been further extended to study the sparse
\(\complexityclass{P}\)-hard set problem for more flexible
reducibilities{}~\cite{cj96-02-04,cj96-02-13}\@. A very interesting
open question in this regard is whether \(\complexityclass{P}\) having
sparse hard sets under logspace Turing reductions collapses
\(\complexityclass{P}\)\@.
%
\asection{5}{Acknowledgment}
%
\apar{5-1}
The author would like to thank Eric Allender, Jin-yi Cai, Lane
Hemaspaandra, Ioan Macarie, D. Sivakumar, and Marius Zimand for
enjoyable discussions, and anonymous referees for many invaluable
comments\@.
%
\end{articletext}
%
\begin{articlebib}
%
\bibliographystyle{\the\rbibstyle}
\bibliography{cj96-02}
%
\end{articlebib}
%
\end{document}