% 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 \(i0\), 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