% The Chicago Journal of Theoretical Computer Science, Volume 1998, Article 1
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1998 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\documentclass[v1.1,published]{cjstruct}
%
% Local style resources for this article.
%
\usestyleresource{amstext}
%
% Local macro definitions for this article.
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\ifx\nopagebreakendpar\undeftex
  \newcommand{\nopagebreakendpar}{\@endparpenalty10000}
\fi
\ifx\nopagebreakinteritem\undeftex
  \newcommand{\nopagebreakinteritem}{\@itempenalty10000}
\fi
\catcode`\@=12
%
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}

\newcommand{\GF}{{\rm GF}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\F}{{\bf F}}

\newcommand{\iso}{\cong}
\newcommand{\implies}{\mbox{\(\;\Longrightarrow\;\)}}
\renewcommand{\iff}{\mbox{\(\;\Longleftrightarrow\;\)}}
\newcommand{\Prob}[1]{{\rm {\bf Pr}}{\bf [} #1 {\bf ]}}
\newcommand{\set}[2]{\{\,#1\mid#2\,\}}
\newcommand{\Vector}[1]{\mbox{\boldmath \(#1\)}}

\newcommand{\BPE}{{\rm BPE}}
\newcommand{\oneBPE}{{\rm 1\mbox{-}BPE}}
\newcommand{\BPI}{{\rm BPI}}
\newcommand{\BPNI}{\mbox{{\rm BPNI}}}
\newcommand{\oneBPI}{{\rm 1\mbox{-}BPI}}
\newcommand{\oneBPNI}{\mbox{{\rm 1\mbox{-}BPNI}}}
\newcommand{\GI}{{\rm GI}}
\newcommand{\GNI}{\mbox{{\rm GNI}}}

\newcommand{\BP}{{\rm BP}}
\newcommand{\RP}{{\rm RP}}
\newcommand{\PH}{{\rm PH}}
\newcommand{\NP}{{\rm NP}}	
\newcommand{\IP}{{\rm IP}}	
\newcommand{\AM}{{\rm AM}}	
\newcommand{\co}{\mbox{\rm co}}	

\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1998, Article 1\\
      \textit{10 March 1998}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, Five Cambridge Center, Cambridge, MA
  02142-1493 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://mitpress.mit.edu/CJTCS/}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{ftp://mitpress.mit.edu/pub/CJTCS}
    \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs}
  \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 1998 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 & Ted Herman & Alan Selman \\
        Jin-Yi Cai & Stephen Homer & Nir Shavit \\
        Anne Condon & Neil Immerman & 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{1998}
%
\articleid{1}
%
\selfcitation{
     @article{cj98-01,
       author={Thomas Thierauf},
       title={The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1998},
       number={1},
       publisher={MIT Press},
       month={March},
       year={1998}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits}
\shorttitle{The Isomorphism Problem}
%
\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{Thomas Thierauf}
   \collname{}{Thierauf, Thomas}
   \begin{institutioninfo}
       \instname{Universit\"at Ulm}
       \department{Abt. Theoretische Informatik}
       \address{Oberer}{Eselsberg}{89069}{Ulm}{Germany}
   \end{institutioninfo}
   \email{thierauf@informatik.uni-ulm.de}
\end{authorinfo}
%
\shortauthors{Thierauf}
%
\support{
Supported in part by DAAD, Acciones Integradas\@.
}
%
\begin{editinfo}
\submitted{11}{2}{1997}\reported{15}{4}{1997}
\submitted{28}{8}{1997}\reported{28}{10}{1997}
\submitted{18{}11}{1997}\reported{24}{11}{1997}
\submitted{26}{11}{1997}\reported{2}{1}{1998}\published{10}{3}{1998}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
\apar{Abstract-1}
We investigate the computational complexity of the 
isomorphism problem for read-once branching programs (1-BPI):
upon input of two read-once branching programs \(B_0\) and \(B_1\),
decide whether there exists a permutation of the variables of \(B_1\)
such that it becomes equivalent to \(B_0\)\@.
%
\apar{Abstract-2}
Our main result is that
\(\oneBPI\) cannot be NP-hard unless the polynomial hierarchy collapses\@.
The result is extended to the isomorphism problem for arithmetic circuits 
over large enough fields\@.
%
\apar{Abstract-3}
We use the known arithmetization of read-once branching programs
and arithmetic circuits into multivariate polynomials over the rationals\@.
Hence,
another way of stating our result is:
the isomorphism problem for multivariate polynomials over large enough fields
is not NP-hard unless the polynomial hierarchy collapses\@.
%
\apar{Abstract-4}
We derive this result by providing a
two-round interactive proof for the
nonisomorphism problem for multivariate polynomials\@.
The protocol is based on the Schwartz-Zippel theorem
for probabilistically checking polynomial identities\@.
%
\apar{Abstract-5}
Finally, we show that there is a
perfect zero-knowledge interactive proof
for the isomorphism problem for multivariate polynomials\@.
\end{abstract}

\asection{1}{Introduction}
%
\apar{1-1}
An interesting computational issue is to decide
the \emph{equivalence\/} of two given programs
with respect to some computational model
such as
Boolean circuits,
branching programs, or
Boolean formulas\@.
A more general problem is to decide the \emph{isomorphism\/} of two given circuits
(for example), that is,
whether the circuits become equivalent after permuting the input variables
of one of the circuits\@.
Isomorphism is one way of formalizing the idea that two circuits
are ``almost'' equivalent\@.
%
\apar{1-2}
The isomorphism problem for Boolean circuits is in fact a very old one,
dating back to the last century 
(see~\cite{cj98-01-10} for background and early references on this problem
and variants of it)\@.
More recently,
the problem has been reconsidered with respect to its 
computational complexity (see, for example, \cite{cj98-01-01,cj98-01-09,cj98-01-10,cj98-01-12})\@.
%
\apar{1-3}
The equivalence problems for Boolean circuits,
branching programs, and Boolean formulas are known to be coNP-complete\@.
Asking for isomorphism roughly amounts to putting
an existential quantifier in front of the problem\@.
Therefore, the corresponding isomorphism problems are in the
second level of the polynomial hierarchy, \(\Sigma^p_2\)\@.
An obvious question is whether these isomorphism problems
are complete for \(\Sigma^p_2\)\@.
This question was solved by Agrawal and Thierauf~\cite{cj98-01-01},
who showed that none of these isomorphism problems
is complete for \(\Sigma^p_2\) 
unless the polynomial hierarchy collapses\@.
Thus, loosely speaking,
the existential quantifier we get by seeking an isomorphism
does not seem to add full NP-power to the corresponding equivalence problem\@.
%
\apar{1-4}
The most prominent example that supports the latter observation
might be the \emph{graph isomorphism problem}, GI\@.
Here,
the equivalence problem for graphs,
which is in fact an equality problem, is trivially
solvable in polynomial time;
therefore, GI is in NP\@.
However, GI is not NP-complete
unless the polynomial hierarchy collapses~\cite{cj98-01-16,cj98-01-08}
(see also~\cite{cj98-01-21})\@.
%
\apar{1-5}
For a restricted class of branching programs, namely, 
the \emph{read-once branching programs},
where on each path, each variable is tested at most once
(see the next section for precise definitions),
the equivalence problem is easier: 
it can be efficiently solved by a randomized Monte-Carlo type algorithm~\cite{cj98-01-07}
with one-sided error,
and is in the complexity class coRP\@.
Therefore,
when an existential quantifier is put in front,
the isomorphism problem for read-once branching programs, \(\oneBPI\),
is in NP\(\cdot\)coRP\@.
Motivated by the examples above,
we ask whether \(\oneBPI\) is NP-hard\@.
%
\apar{1-6}
In this paper, we show that 
\(\oneBPI\) is also in the Arthur-Merlin class, \(\co\AM = \BP \cdot \co\NP\)\@.
As a consequence, it is not NP-hard
unless the polynomial hierarchy collapses\@.
The result is extended to \emph{arithmetic circuits\/} (or \emph{straight-line programs\/})
over large enough fields\@.
%
\apar{1-7}
One crucial point required to prove these results is that both 
read-once branching programs and arithmetic circuits
can be arithmetized, yielding equivalent multivariate polynomials~\cite{cj98-01-07,cj98-01-19}\@.
In the case of read-once branching programs,
these polynomials are multilinear\@.
Therefore,
our main results can be restated in purely algebraic terms:
the isomorphism problem for multivariate polynomials
over large enough fields is not NP-hard
unless the polynomial hierarchy collapses\@.
%
\apar{1-8}
Our proof is based on a two-round interactive proof for  
the nonisomorphism problem for multivariate polynomials\@.
In principle,
the interactive proof protocol follows the one for \emph{graph nonisomorphism}, GNI\@.
However,
there is a crucial difference:
in our protocol,
the verifier needs to compute a normal form of a polynomial
to hide the syntactic structure of the input polynomials
that are manipulated\@.
This problem does not occur when working with graphs;
however,
this requirement seems to exceed the computational power of the verifier\@.
We get around this difficulty by computing a 
\emph{randomized normal form\/} instead\@.
The randomized normal form is based on the Schwartz-Zippel theorem
for testing polynomial identities\@.
%
\apar{1-9}
Combining these ideas with the ones from
Goldreich, Micali, and Wigderson~\cite{cj98-01-16},
we obtain perfect zero-knowledge interactive proofs for  these
isomorphism problems\@.
%
\apar{1-10}
An extension of an isomorphism is a  \emph{congruence},
where in addition to permuting variables, one can exchange a variable
with its negation\@.
Although we formulate our results only for isomorphism problems,
it can easily be checked that 
all our theorems also hold for  
the corresponding congruence problems\@.

\asection{2}{Preliminaries}

\asubsection{2.1}{Basic Definitions}
%
\apar{2.1-1}
We use fairly standard notions of complexity theory\@.
We refer the reader to~\cite{cj98-01-04,cj98-01-05,cj98-01-18} for definitions 
of complexity classes such as P, NP, RP, or BPP\@.
The \(k^\mathrm{th}\) level of the polynomial hierarchy is denoted by \(\Sigma^p_k\)\@.
For any class \({\cal C}\),
we denote the complement class by \(\co\ {\cal C}\)\@.
%
\apar{2.1-2}
Class \(\BP\cdot\NP\) 
is the class of sets~\(L\) such that there exist 
a set \(A\in\NP\) and a polynomial~\(p\)  
such that for every \(x\):
\begin{eqnarray*}
x \in L & \implies & \Prob{(x, y) \in A} ~=~ 1\\
x \not\in L & \implies & \Prob{(x, y) \in A} ~\leq~ {1 \over 2}
\end{eqnarray*}
where \(y\) is chosen uniformly at random from \(\Sigma^{p(|x|)}\)\@.
The obvious definition of \(\BP\cdot\NP\) would be with two-sided error,
but this is equivalent with the definition given here\@.
%
\apar{2.1-3}
Class \(\NP \cdot \co\RP\) is the class of sets~\(L\) such that there exist
a set \(A\in\co\RP\) and a polynomial~\(p\)  
such that for every \(x\), we have:
\begin{eqnarray*}
x \in L & \iff & \exists y \in \Sigma^{p(|x|)}:~(x, y) \in A
\end{eqnarray*}
%
\apar{2.1-4}
Interactive proofs were defined in~\cite{cj98-01-15}\@. 
An interactive proof system for a set \(L\)
consists of a prover~\(P\) and a verifier~\(V\)\@.
The verifier is a randomized polynomial-time algorithm
that can communicate with the prover\@.
The prover can make arbitrary computations\@.
After following some communication protocol,
the verifier finally has to accept or reject a given input,
such that:
\begin{eqnarray*}
x \in L & \implies & \exists\ \mbox{prover } P:~ \Prob{(V,P)(x) \mbox{ accepts}} ~=~ 1\\
x \not\in L & \implies & \forall\ \mbox{prover } P:~  \Prob{(V,P)(x) \mbox{ accepts}} ~\leq~{1 \over 2}
\end{eqnarray*}
where the probability is taken over the random choices
of the verifier\@.
%
\apar{2.1-5}
Class \(\IP\) is the class of sets that have an interactive proof system,
and \(\IP[k]\) is the subclass of \(\IP\) where
the verifier and the prover exchange at most \(k\) messages\@.
%
\apar{2.1-6}
Arthur-Merlin games were introduced in~\cite{cj98-01-03}\@.
They are defined similarly to interactive proofs, with 
Arthur corresponding to the verifier and 
Merlin to the prover\@.
The only difference is that Arthur has to make his random bits available to Merlin,
whereas in the interactive proof model, 
the prover does not know the random bits of the verifier\@.
The notation \(\AM[k]\) denotes when \(k\) messages can be sent, and
\(\AM = \AM[2]\)\@.
%
\apar{2.1-7}
In this paper,
we are interested in constant-round interactive proof systems\@.
It is known that for both
interactive proof systems and Arthur-Merlin games,
constantly many rounds are the same as one round:
for any~\(k \geq 2\), \(\IP[k] = \AM[k] = \AM\)~\cite{cj98-01-03,cj98-01-17}\@.
Moreover,
it is known that
\(\AM = \BP \cdot \NP\)\@.
%
\apar{2.1-8}
An IP protocol for a set~\(L\) is a \emph{perfect zero-knowledge\/} protocol~\cite{cj98-01-15}
if it decides \(L\) correctly in the usual way and, in addition,
for any \(x \in L\),
the prover does not reveal any extra information to any verifier~\(V^*\)
besides the fact that \(x\) is in \(L\):
the messages exchanged with the prover appear random to \(V^*\)
(that is, these messages could have been produced by \(V^*\) himself)\@.
%
\apar{2.1-9}
\begin{alabsubtext}{Definition}{1}{}
\apar{Definition 1-1}
A prover \(P\) is perfectly zero knowledge on \(L\)
if, for any interactive machine \(V^*\) running in expected polynomial time, 
there is a probabilistic machine \(M_{V^*}\) running in expected polynomial time 
such that
for any \(x \in L\) and any string~\(H\), \(|H| \leq |x|^c\) for some \(c>0\),
and the communication between \(P\) and \(V^*\) on input \((x,H)\),
seen as a random variable, is identically distributed to the output of \(M_{V^*}\)
on the same input\@.
%
\apar{Definition 1-2}
Together, \(P\) and \(V\) form a perfect
 zero-knowledge proof system for \(L\)
if the system is an interactive proof system for \(L\), and
if \(P\) is perfectly zero knowledge on \(L\)\@.
\end{alabsubtext}
%
\apar{2.1-10}
The string~\(H\) in the definition is needed if we wish to combine
two zero-knowledge protocols into one zero-knowledge protocol:
the history~\(H\) from the first protocol,
which is known to the verifier in the second protocol,
does not help the verifier\@.
For a more detailed discussion of this definition 
and the need for expected polynomial time,
see~\cite{cj98-01-15,cj98-01-16}\@.

\asubsection{2.2}{Verifying Polynomial Identities}
%
\apar{2.2-1}
Let \(\F\) be some field, and \(p = p(x_1, \dots, x_n)\) be a multivariate
polynomial over \(\F\)\@.
The \emph{degree\/} of \(p\) is the maximum exponent of any variable
when \(p\) is written as a sum of monomials\@.
Polynomials of degree~\(1\) are called \emph{multilinear}\@.
Note the difference from the \emph{total degree} of a polynomial, 
where one first adds the exponents of the variables in each monomial 
and then takes the maximum over these sums\@.
%
\apar{2.2-2}
Given some polynomial~\(p\) written as an arithmetic expression,
we want to find out whether \(p\) is in fact the zero polynomial\@.
The obvious algorithm, 
namely, to transform the arithmetic expression in a sum of monomials
and check whether all coefficients are zero,
can have up to exponential running time (in the size of the input)\@.
Efficient \emph{probabilistic\/} zero tests were developed by
Schwartz~\cite{cj98-01-22} and Zippel~\cite{cj98-01-24}\@.
The version below is a variant shown by Ibarra and Moran~\cite{cj98-01-19}\@.
They extended the corresponding theorem for multilinear polynomials
shown by Blum, Chandra, and Wegman~\cite{cj98-01-07} to arbitrary degrees\@.
We give a proof for completeness\@.
%
\begin{alabsubtext}{Theorem}{1}{\rm {\bf \cite{cj98-01-19,cj98-01-22,cj98-01-24}}}
Let \(p(x_1, \dots, x_n)\) be a multivariate polynomial of degree~\(d\) over field \(\F\)
that is not the zero polynomial\@.
Let \(T \subseteq \F\) with \(|T| \geq d\)\@.
Then there are at least \((|T|-d)^n\) points \((a_1, \dots, a_n) \in T^n\)
such that \(p(a_1, \dots, a_n) \not= 0\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
The proof is by induction on~\(n\)\@.
For \(n = 1\) the theorem is true, because
a degree-\(d\) polynomial has at most \(d\) roots in \(\F\)\@.
%
\apar{2.2-3}
Let \(n>1\) and let \(p(x_1, \dots, x_n)\) be a nonzero polynomial of degree~\(d\)\@.
Furthermore, let \(\Vector{a} = (a_1, \dots, a_n)\) be a point
such that \(p(\Vector{a}) \not= 0\)\@.
We define two polynomials, both of which are subfunctions of \(p\):
\begin{eqnarray*}
p_0(x_1, \dots, x_{n-1})  &=& p(x_1, \dots, x_{n-1}, a_n)\\
p_1(x_n)  &=& p(a_1, \dots, a_{n-1},x_n)
\end{eqnarray*}
By construction, both polynomials are nonzero
and have degree bounded by~\(d\):
\(p_0\) has \(n-1\) variables, and therefore differs from 0
on at least \((|T|-d)^{n-1}\) points in \(T^n\) (by the induction hypothesis)\@.
Similarly,
\(p_1\) has one variable, and therefore has at least \(|T|-d\) nonzero points\@.
%
\apar{2.2-4}
For each of the \(|T|-d\) choices for \(a_n\) where \(p_1\) is nonzero,
the corresponding polynomial~\(p_0\) has \((|T|-d)^{n-1}\) 
nonzero points\@.
Therefore,
the number of nonzero points of \(p\) in \(T^n\) is at least
\((|T|-d)(|T|-d)^{n-1}  = (|T|-d)^n\)\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{2.2-5}
We mention two important consequences of this theorem\@.
First of all, let \(T\) be any subset of \(\F\) that has at least \(d+1\) elements\@.
Then any nonzero polynomial of degree \(d\) has a nonzero point in \(T^n\)\@.
%
\begin{alabsubtext}{Corollary}{1}{}
Let \(p(x_1, \dots, x_n)\) be a polynomial of degree~\(d\) over \(\F\),
and \(T \subseteq \F\) with \(|T| > d\)\@.
Then \(p \not\equiv 0 \iff \exists \Vector{a} \in T^n~~p(\Vector{a}) \not= 0\)\@.
\end{alabsubtext}
%
\apar{2.2-6}
By enlarging \(T\) even further,
we can show that any nonzero polynomial \(p\) does not vanish 
on most of the points of \(T^n\)\@.
This provides the tool for the probabilistic zero test\@.
%
\begin{alabsubtext}{Corollary}{2}{}
Let \(p(x_1, \dots, x_n)\) be a polynomial of degree~\(d\) over \(\F\),
and \(T \subseteq \F\) with \(|T| \geq 2nd\)\@.
Let \(\Vector{r} = (r_1, \dots, r_n)\) be a random element from \(T^n\)\@.
Then \(p(\Vector{r}) \not= 0\), with probability at least \(1/2\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Corollary}{2}{}
\prooffontshape
\[
	\Prob{p(\Vector{r}) \not= 0} 
	\geq  \left({|T| - d \over |T|} \right)^n
	\geq  \left(1-{1 \over 2n}\right)^n
	\geq {1 \over 2}
\]
{\nopagebreakbeginpar\markendlst{Proof of Corollary 2}}
\end{alabsubtext}

\asubsection{2.3}{Branching Programs}
%
\apar{2.3-1}
A \emph{branching program} \(B\) in \(n\) Boolean variables \(x_1, \dots, x_n\)
is a directed acyclic graph with the following types of nodes\@.
There is a single node of indegree zero, the \emph{initial node of\/} \(B\)\@.
All nodes have outdegree two or zero\@.
A node with outdegree two is an \emph{internal node of} \(B\)\@.
One of its edges is labeled with \(x_i\), the other with \(\overline{x}_i\),
for some \(i \in \{1, \dots, n\}\)\@.
A node with outdegree zero is a \emph{final node of} \(B\)\@.
The final nodes are labeled by either \emph{accept} or \emph{reject}\@.
%
\apar{2.3-2}
We call a branching program \emph{read-once}
if, on each path from the initial node to a final node,
every variable or its complement occurs at most once as an edge label\@.
%
\apar{2.3-3}
A read-once branching program is called \emph{ordered}
if the order of variable occurence on each path is consistent
with some ordering on the set of variables\@.
%
\apar{2.3-4}
Branching programs are also called \emph{binary decision diagrams} (BDD)
or \emph{Boolean graphs\/}\@.
Read-once branching programs 
and ordered branching programs 
are also called \emph{free binary decision diagrams} (FBDD) or \emph{free Boolean graphs}
and \emph{ordered binary decision diagrams} (OBDD), respectively\@.
%
\apar{2.3-5}
A branching program~\(B\)  defines an
\(n\)-ary Boolean function from \(\{0,1\}^n\) to \(\{0,1\}\) as follows\@.
For an assignment \(\Vector{a} = (a_1, \dots, a_n) \in \{0,1\}^n\),
we walk through~\(B\), starting at the initial node, always following
the (unique) edge that evaluates to one under \(\Vector{a}\),
until we reach a final node\@.
If the final node is an accepting node, we define \(B(\Vector{a}) =1\),
and \(B(\Vector{a}) =0\) otherwise\@.
%
\apar{2.3-6}
Two  branching programs \(B\) and \(B'\) in \(n\)~variables are equivalent,
\(B \equiv B'\) for short,
if they define the same Boolean function\@.
By \(\BPE\)
we denote the problem of deciding
whether two given branching programs are equivalent\@.
That is,
\[\BPE = \set{(B,B')}{B \equiv B'}\]
It is not hard to see that branching programs can compute
CNF Boolean formulas\@.
Therefore,
the satisfiability problem for branching programs is NP-complete;
hence \(\BPE\) is coNP-complete\@.
%
\apar{2.3-7}
Blum, Chandra, and Wegman~\cite{cj98-01-07} showed
that the equivalence problem for read-once branching programs, \(\oneBPE\),
is easier because one can transform these programs into equivalent
multilinear polynomials over the rational numbers, \(\Q\)\@.
To see this,
note first that a branching program~\(B\) can be viewed as a compact
way of denoting a DNF formula \(F_B\):
each path of ~\(B\) can be written as a monomial,
the conjunction of the literals occurring along that path\@.
Then, the function computed by~\(B\) is simply
the disjunction of all monomials coming from accepting paths of~\(B\)\@.
%
\apar{2.3-8}
We convert \(F_B\) into a polynomial~\(p_B\) over the rational numbers \(\Q\) as follows\@.
A variable \(x_i\) is kept as \(x_i\)\@.
A negated variable \(\overline{x}_i\) is replaced by \(1-x_i\)\@.
A conjunction is replaced by multiplication,
and a disjunction is replaced by addition\@.
For each satisfying assignment~\(\Vector{a} \in \{0,1\}^n\),
exactly one path of \(B\) evaluates to true under~\(\Vector{a}\)\@.
Therefore,
at most one product term in \(p_B\) will be one on input~\(\Vector{a}\);
hence, \(B\) and \(p_B\) agree on \(\{0,1\}^n\)\@.  That is,
\[ B(\Vector{a}) = p_B(\Vector{a})~~\mbox{ for all } \Vector{a} \in \{0,1\}^n\]
It is easy to get an arithmetic expression for \(p_B\) from \(B\)
that has about the same size as \(B\)\@.
Note, however, that when
written as a sum of monomials,
\(p_B\) may consist of exponentially many terms in the size of \(B\)\@.
Therefore, in general, we cannot write down \(p_B\) in this normal form in polynomial time in \(|B|\)\@.
However,
with the expression at hand,
we can evaluate \(p_B\) at a given point in \(\Q^n\) in polynomial time,
and this suffices for our purposes\@.
To evaluate \(p_B\) at a point~\(\Vector{a} = (a_1, \dots, a_n)\),
we start by writing a 1 at the initial node\@.
Suppose now that a node has value~\(v\),
and its edges are labeled by variable \(x_i\)\@.
Then, values \(v a_i\) and \(v(1-a_i)\) are sent along
the \(x_i\)- and \(\overline{x}_i\)-edges, respectively\@.
When all incoming edges of a node \(u\) have sent values,
the value of \(u\) is the sum of all these incoming values\@.
Finally,
the value of \(p_B\) appears at the accepting node\@.
%
\apar{2.3-9}
Since \(B\) is read-once,
\(p_B\) is a multilinear polynomial\@.
Next let \(B'\) be another read-once branching program, and let \(p_{B'}\)
be the corresponding polynomial\@.
If \(B\) and~\(B'\) are equivalent,
then \(p_B\) and~\(p_{B'}\) agree on \(\{0,1\}^n\), a two-element set\@.
By Corollary~1 (applied to \(p = p_B - p_{B'}\)),
it follows that \(p_B\) and~\(p_{B'}\) agree on \(\Q\)\@.
Choosing \(T\) in Corollary~2 as \(T = \{1, \dots, 2n\}\),
we detect an inequivalence with probability more than \(1/2\)\@.
It follows that \(\oneBPE \in \co\RP\)\@.
%
\apar{2.3-10}
Fortune, Hopcroft, and Schmidt~\cite{cj98-01-13} have shown that if
one of two given read-once branching programs is even ordered,
then the equivalence can be decided in polynomial time\@.
In particular,
the equivalence problem for ordered branching programs
is solvable in polynomial time\@.
%
\apar{2.3-11}
Two  branching programs~\(B\) and~\(B'\) are isomorphic,
denoted by \(B \iso B'\),
if there exists a permutation~\(\varphi\) on \(\{x_1, \dots, x_n\}\)
such that \(B\) becomes equivalent to \(B'\) when permuting the variables of \(B'\)
according to \(\varphi\)\@.
That is, \(B \equiv  B' \circ \varphi\)\@.
In this case,
we call \(\varphi\) an \emph{isomorphism between \(B\) and~\(B'\)}\@.
%
\apar{2.3-12}
The isomorphism problem for branching programs is:
\begin{eqnarray*}
\BPI &=& \set{(B,B')}{B \iso B'}
\end{eqnarray*}
The isomorphism problem for read-once branching programs, \(\oneBPI\),
is defined analogously\@.
It follows directly from the definition that \(\BPI \in \Sigma_2^p\),
the second level of the polynomial hierarchy\@.
Agrawal and Thierauf~\cite{cj98-01-01} showed that \(\BPNI\)
is in \(\BP \cdot \Sigma_2^p\)\@.
By a result of Sch{\"o}ning~\cite{cj98-01-21},
it follows that \(\BPI\) cannot be complete for \(\Sigma_2^p\)
unless the polynomial hierarchy collapses to its third level, \(\Sigma_3^p\)\@.
%
\apar{2.3-13}
For read-once branching programs,
we have \(\oneBPI \in \NP \cdot \co\RP\)\@.
An obvious question is whether \(\oneBPI\) is NP-hard\@.
In this paper,
we show that the problem of deciding whether two read-once branching programs are not
isomorphic, \(\oneBPNI\),
is in \(\BP \cdot \NP\)\@.
Combined with the result of Boppana, H{\aa}stad, and Zachos~\cite{cj98-01-08} 
(see also Sch{\"o}ning~\cite{cj98-01-21}),
it follows that \(\oneBPI\) cannot be \(\NP\)-hard
unless the polynomial hierarchy collapses to its second level, \(\Sigma_2^p\)\@.
%
\apar{2.3-14}
This result also covers the case of ordered branching programs\@.
Note, however, that in that case, the isomorphism problem is in NP\@.

\asubsection{2.4}{Arithmetic Circuits}
%
\apar{2.4-1}
An \emph{arithmetic circuit over a field\/}~\(\F\) is a circuit
where the inputs are field elements,
and the (fan-in two) gates perform the field operations \(+\), \(-\), and \(\times\)\@.
(We could also allow division, as long as a circuit
guarantees not to divide by zero on any input\@.)
Circuit size and depth are defined as usual\@.
%
\apar{2.4-2}
Ibarra and Moran~\cite{cj98-01-19} considered the equivalence problem for arithmetic circuits
(called straight-line programs there)\@.
They gave probabilistic polynomial-time algorithms for circuits over infinite fields\@.
This was split into two cases,
depending on whether the field had characteristic of 0 or greater than 0\@.
If the field \(\F\) had characteristic 0, it contained a subfield
isomorphic to \(\Q\), the rational numbers\@.
Therefore, it is enough to consider \(\F =\Q\)\@.
We show how a zero test can be done in this case\@.
%
\apar{2.4-3}
If a circuit~\(C\) has \(n\) input variables \(x_1, \dots, x_n\),
then \(C\) computes a multivariate polynomial~\(p_C\) over \(\Q\)\@.
If \(C\) has depth~\(d\), then \(p_C\) has degree at most \(2^d\)\@.
Therefore,
to obtain a zero test for~\(p_C\),
we have to choose \(T\) in Corollary~2 as \(T = \{1, \dots, 2n2^d\}\)
to detect a nonzero point with probability more than \(1/2\)
at a random point from \(T^n\)\@.
%
\apar{2.4-4}
However,
we do not have a polynomial-time procedure yet, because
the function values of \(p_C\) on \(T^n\) could be as large as \((2n2^d)^{n2^d} \leq 2^{N 2^N}\)
for \(N = n d\)\@.
Represented in binary, such numbers would be exponentially long\@.
Instead,
we evaluate \(p_C\) modulo smaller numbers,
namely from \(M=\{1, \dots, 2^{2N}\}\)\@.
(For a zero test, we can assume that all coefficients are integers,
so that the function values of \(p_C\) are integers too\@.)
Notice that \(p_C \pmod m\) might have more zeros than \(p_C\),
however, not too many:
%
\begin{alabsubtext}{Lemma}{1}{\cite{cj98-01-19}}
For any \(y \leq 2^{N 2^N}\) and a randomly chosen \(m \in M\),
we have \(y \not\equiv 0 \pmod m\) with probability at least \({1 \over 3N}\),
for large enough \(N\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{1}{}
\prooffontshape
Any  \(y \leq 2^{N 2^N}\) has at most  \(N 2^N\) prime divisors\@.
By the prime-number theorem, there are more than \({2^{2N} \over 2N}\)
primes in \(M\) for large enough \(N\)\@.
Therefore, \(M\) contains at least \({2^{2N} \over 2N} - N 2^N\)
primes that do not divide \(y\)\@.
Hence, for \(m\) randomly chosen from \(M\), we have:
\[\Prob{y \not\equiv 0 \pmod m} 
\geq {{2^{2N} \over 2N} - N 2^N \over  2^{2N}}
= {1 \over 2N} - {N \over 2^{N}}
\geq {1 \over 3N}\]
{\nopagebreakbeginpar\markendlst{Proof of Lemma 1}}
\end{alabsubtext}
%
\apar{2.4-5}
The probabilistic zero test now works as follows\@.
%
\begin{alabsubtext}{Corollary}{3}{}
Let \(p(x_1, \dots, x_n)\) be a nonzero polynomial of degree~\(2^d\) over \(\Q\),
\(T = \{1, \dots, 2n2^d\}\), and \(M=\{1, \dots, 2^{2N}\}\), where \(N=nd\)\@.
Choose \(\Vector{r}_1, \dots, \Vector{r}_{6N}\) from \(T^n\)
and \(m_1, \dots, m_{6N}\) from \(M\), independently at random\@. 
Then, \(p(\Vector{r}_i) \not\equiv 0 \pmod {m_i}\), for some \(i\),
with probability at least \(1/2\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Corollary}{3}{}
\prooffontshape
By Corollary~2 and Lemma~1:
\[
\Prob{p(\Vector{r}_i) \not\equiv 0 \pmod {m_i}} \geq {1 \over 2} {1 \over 3N},
\mbox{ for any pair } \Vector{r}_i, m_i
\]
Therefore,
\[
\Prob{p(\Vector{r}_i) \equiv 0 \pmod {m_i} \mbox{ for all \(i\) }} 
\leq \left(1-{1 \over 6N}\right)^{6N}
\leq {1 \over 2}
\]
{\nopagebreakbeginpar\markendlst{Proof of Corollary 3}}
\end{alabsubtext}
%
\apar{2.4-6}
We only sketch briefly the case of infinite fields with finite characteristic,
and refer the reader to~\cite{cj98-01-19} for a more detailed treatment\@.
Let \(\F\) be a field with characteristic~\(q\)
(which must, therefore, be a prime number)\@.
The trick is then to switch from \(\F\) to the ring of polynomials over \(\GF(q)\)\@.
This is certified by the the following lemma\@.
%
\begin{alabsubtext}{Lemma}{2}{\rm {\bf \cite{cj98-01-19}}}
Let \(p(x_1, \dots, x_n)\) be a polynomial\@.
\(p \equiv 0\) over \(\F\) if and only if \(p \equiv 0\) over \(\GF(q)[x]\)\@.
\end{alabsubtext}
%
\apar{2.4-7}
Since \(q\) is prime, \(\GF(q)\) is a field; therefore,
the ring \(\GF(q)[x]\) is a principal ideal domain,
that is, a ring with a one and no zero divisors such that every ideal is principal\@.
(In fact, \(\GF(q)[x]\) is what is sometimes called a \emph{Euclidean ring\/}\@.)
One can easily verify that this already suffices
in the assumption of Theorem~1 and its corollaries,
instead of having a field\@.
Hence,
we can apply the zero test for \(p\) over the polynomial ring \(\GF(q)[x]\)\@.
%
\apar{2.4-8}
However,
we can only deal with polynomials up to polynomial size in the input length\@.
In the case of \(\Q\), we did computations modulo small enough prime numbers\@.
Now we do computations modulo polynomials of small degree\@.
There is an analog of Lemma~1 bounding the 
probability that \(p(a_1, \dots a_n) \not= 0\), 
but \(p(a_1, \dots a_n) = 0 \pmod {r}\) 
for a randomly chosen  polynomial~\(r \in \GF(q)[x]\) of small degree
and \(a_i \in \GF(q)[x]\), for \(i = 1, \dots, n\)\@.
%
\apar{2.4-9}
Putting things together,
we get a zero test analogous to the one for polynomials over \(\Q\),
only the domain has changed to a polynomial ring instead of numbers\@.
%
\apar{2.4-10}
Clearly,
for any polynomial~\(p\) in \(\F[x_1, \dots, x_n]\)
given as an arithmetic expression,
one can construct an arithmetic circuit computing~\(p\)
that has about the same size as~\(p\)\@.
In particular,
it follows from the discussion in the preceding section
that one can transform a read-once branching program
into an equivalent arithmetic circuit of about the same size\@.
Though arithmetic circuits are the more general concept,
we prove our main result for read-once branching programs first,
and then explain how to extend it to solve the 
isomorphism problem for arithmetic circuits\@.

\asection{3}{An Interactive Proof for 1-BPNI}
%
\apar{3-1}
We show that there is a two-round interactive proof for 
the nonisomorphism problem for 
read-once branching programs, \(\oneBPNI\)\@.
%
\apar{3-2}
We start by recalling the idea of the interactive proof for
the graph nonisomorphism problem, GNI~\cite{cj98-01-15} (see also \cite{cj98-01-20})\@.
There,
on input of two graphs \(G_0\) and \(G_1\), 
the verifier randomly picks \(i \in \{0,1\}\)
and a permutation~\(\varphi\),
and sends \(H = \varphi(G_i)\) to the prover\@.
The prover is then asked to find out what the value of \(i\) is\@.
The verifier will accept only if the prover gives the right answer\@.
%
\apar{3-3}
When the input graphs are not isomorphic, 
then the prover can identify~\(i\) easily\@.
However,
when the graphs are isomorphic,
both could have been used by the verifier to compute~\(H\),
so that  no prover can identify~\(i\)\@.
For this reason, the answer of any prover is
correct with probability at most \(1/2\)\@.
%
\apar{3-4}
First of all, note that we cannot directly adapt this protocol
to branching programs\@.
The reason is that the syntactic structure
of two given isomorphic branching programs 
might tell the prover which of two given  branching programs 
was selected by the verifier,
at least, if the verifier simply exchanges variables according to some permutation\@.
%
\apar{3-5}
A way out of this would be a normal form for read-once branching programs
that is easy to compute;
however,
such a normal form is not known\@.
At this point,
in the case of general branching programs,
Agrawal and Thierauf~\cite{cj98-01-01} used a result from learning theory 
by Bshouty et al.~\cite{cj98-01-11}:
there is a randomized algorithm that uses an NP-oracle and  
outputs branching programs equivalent to a given one\@.
The important point is that although
the algorithm might output (syntactically) different branching programs
depending on its random choices,
the output does not depend on the syntactic structure of its input\@.
However,
in our case,
the verifier does not have an NP-oracle available,
and there is no analog learning result
for read-once branching programs without an NP-oracle\@.
%
\apar{3-6}
The idea for getting around this problem is as follows\@.
On input of two given read-once branching programs \(B_0\) and \(B_1\)
with \(n\) variables,
the verifier randomly chooses one of them and permutes it
with a random permutation to obtain a branching program \(B\)\@.
Instead of trying to manipulate all of \(B\),
the verifier takes the arithmetization~\(p_B\) of \(B\) and
evaluates \(p_B\) at a randomly chosen point~\(\Vector{r} \in T^n\),
where \(T\) is some appropriate test domain\@.
The prover is then asked to tell which of \(B_0\), \(B_1\)
was used to obtain the point \((\Vector{r},p_B(\Vector{r}))\)\@.
If \(B_0\) and \(B_1\) are isomorphic,
then the prover cannot detect this, and must guess;
it will fail with probability \(1/2\)\@.
On the other hand,
if \(B_0\) and \(B_1\) are not isomorphic,
then the prover has a good chance of detecting
the origin of \((\Vector{r},p_B(\Vector{r}))\)\@.
This is because, by Corollary~2,
different multilinear polynomials
can agree on \(T\) on at most \(1/2\) of the points
for \(|T| \geq 2n\)\@.
That is,
the origin of \((\Vector{r},p_B(\Vector{r}))\) is unique with high probability\@.
With an additional round of communication,
the prover can always convince the verifier
of the nonisomorphism of \(B_0\) and \(B_1\)\@.
We give the details below\@.
%
\begin{alabsubtext}{Theorem}{2}{}
\(\oneBPNI \in \IP[4]\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
We give a protocol for \(\oneBPNI\)\@.
The  inputs are two read-once branching programs \(B_0\), \(B_1\),
both in \(n\) variables\@. Let \(T = \{1, \dots, 2n\}\)\@.
%
\begin{description}
\item[V1:] 
The verifier randomly picks 
\(i \in \{0,1\}\), 
a permutation~\(\varphi\), and
\(\Vector{r}_1, \dots, \Vector{r}_k \in T^n\),
where \(k = \lceil n \log n \rceil +2\)\@.
Then it permutes the variables of \(B_i\)
according to \(\varphi\), 
computes \(y_l = p_{B_i} \circ \varphi (\Vector{r}_l)\) for \(l = 1, \dots,k\),
and sends the set of pairs \(R = \set{(\Vector{r}_l,y_l)}{l = 1, \dots,k}\)
to the prover\@.
\item[P1:]
The prover sends
\(j \in \{0,1\}\) and 
a  permutation~\(\varphi'\) to the verifier\@.
\item[V2:] 
If \(i=j\), then the verifier accepts\@.
If \(i \not= j\), the verifier
checks whether 
\(p_{B_j} \circ \varphi'\) matches the set \(R\), that is, whether
\(p_{B_j} \circ \varphi' (\Vector{r}_l) = y_l\) for \(l = 1, \dots,k\)\@.
If the test fails, the verifier rejects;
otherwise, it sends \(\varphi\) to the prover\@.
\item[P2:]
The prover sends
a point \(\Vector{r}' \in T^n\) to the verifier\@.
\item[V3:] 
Finally,
the verifier accepts if and only if
\(p_{B_i} \circ \varphi (\Vector{r}') \not= p_{B_j} \circ \varphi' (\Vector{r}')\)\@.
\end{description}
%
\apar{3-7}
We show that the above protocol works correctly\@. 
%
\begin{alabsubtext}{Case}{1}{}
\(B_0 \not\iso B_1\): There is a prover such that the verifier always accepts
\end{alabsubtext}
%
The prover can cycle through all permutations
and check whether \(p_{B_0}\) or  \(p_{B_1}\)
match with the set \(R\) sent by the verifier in step~V1\@.
Say that polynomial \(p_{B_0} \circ \varphi'\) matches\@.
The prover then sends \(j = 0\) and \(\varphi'\) to the verifier in step~P1\@.
%
\apar{3-8}
If no permutation of polynomial \(p_{B_1}\) matches \(R\) as well,
then \(i\) must have been \(0\), and therefore, the verifier
will accept in the first round\@.
%
\apar{3-9}
On the other hand,
if some permutation of polynomial \(p_{B_1}\) matches \(R\),
then the prover cannot tell which one was used by the verifier\@.
If the prover is lucky, \(i\) has been zero anyway, and the verifier accepts\@.
On the other hand, if \(i \not= j\),
then the verifier will send \(\varphi\) to the prover in step~V2,
because \(p_{B_j} \circ \varphi'\) matches \(R\)\@.
Since
\(p_{B_j} \circ \varphi'\not= p_{B_i} \circ \varphi\),
these polynomials can agree on at most \(1/2\) of the points of \(T^n\)
by Corollary~2\@.
Therefore,
the prover can find a point \(\Vector{r}' \in T^n\)
such that \(p_{B_j} \circ \varphi'(\Vector{r}') \not= p_{B_i} \circ \varphi(\Vector{r}')\),
and send it  to the verifier  in step~P2, which will accept in step~V3\@.
In summary, the verifier accepts with probability one\@.
%
\begin{alabsubtext}{Case}{2}{}
\(B_0 \iso B_1\): For any prover, the verifier accepts
with probability at most \(3/4\)
\end{alabsubtext}
%
By executing the protocol several times in parallel,
the acceptance probability can be made exponentially small\@.
%
\apar{3-10}
The prover will always find permutations of \(p_{B_0}\) \emph{and\/} \(p_{B_1}\)
that match the set~\(R\) sent by the verifier in step~V1\@.
Therefore,
with respect to the test \(i=j\) made by the verifier,
the best the prover can do is guess \(j\) randomly\@.
This will make the verifier accept with probability \(1/2\) in step~V2\@.
However,
the prover can improve its chances by the condition
checked in the second round by the verifier, i.e., by fixing 
\(i\) and \(\varphi\) chosen by the verifier, say \(i=0\)\@.
Then there might exist a permutation \(\varphi'\)
such that \(p_{B_1} \circ \varphi'\) matches \(R\),
but \(p_{B_0} \circ \varphi \not= p_{B_1} \circ \varphi'\)\@.
Then the prover could choose a point~\(\Vector{r}'\) such that
\(p_{B_0} \circ \varphi(\Vector{r}') \not= p_{B_1} \circ \varphi'(\Vector{r}')\),
and make the verifier accept  in step~V3 by sending
\(j=1\), \(\varphi'\), and \(\Vector{r}'\)\@.
We give an upper bound on the probability of this event\@.
%
\apar{3-11}
By Corollary~2,
for any \(\varphi'\) such that
\(p_{B_0} \circ \varphi \not= p_{B_1} \circ \varphi'\), we have:
\begin{eqnarray*}
\Prob{p_{B_0} \circ \varphi(\Vector{r}) = p_{B_1} \circ \varphi'(\Vector{r})}
&<& {1 \over 2}
\end{eqnarray*}
for a randomly chosen \(\Vector{r} \in T^n\)\@.
Because points \(\Vector{r}_1, \dots, \Vector{r}_k \in T^n\)
are chosen independently and uniformly
at random from \(T^n\),
we have:
\begin{eqnarray*}
\Prob{p_{B_1} \circ \varphi' \mbox{ matches } R} &<& 2^{-k}
\end{eqnarray*}
Therefore, considering all such \(\varphi'\), 
we get that:
\begin{eqnarray*}
\Prob{\exists \varphi'~(p_{B_0} \circ \varphi \not= p_{B_1} \circ \varphi'
\mbox{ and } p_{B_1} \circ \varphi' \mbox{ matches } R}
&< & n!\ 2^{-k} ~\leq~ {1 \over 4}
\end{eqnarray*}
by our choice of \(k\)\@.
We conclude that the probability that any of the conditions tested
by the verifier is satisfied is bounded by \((1/2) + (1/4) = 3/4\)\@.
That is,
the verifier accepts with probability at most \(3/4\),
irrespective of the prover\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%
\apar{3-12}
We can directly reduce to a one-round interactive proof
by choosing \(T\) large, for example \(T = \{1, \dots, 2nn!\}\)\@.
Then,
in case \(B_0 \not\iso B_1\), 
the prover can always find a point \(\Vector{r}'\) (as above) without knowing \(\varphi\),
and hence can already send it in the first round to the verifier,
which can then make all its tests\@.
However,
another difficulty arises:
when \(T\) has exponential size, the values of the polynomials
might be up to double exponential,
in which case the  polynomial time verifier can no longer deal with the numbers\@.
We will show in the next section how the verifier can still
manage its task\@.
%
\apar{3-13}
As mentioned in Section~2.1,
the class of sets that can be decided by a constant-round interactive proof system
coincides with the Arthur-Merlin class AM
which, in turn, is the same as \(\BP \cdot \NP\)~\cite{cj98-01-03,cj98-01-17}\@.
%
\begin{alabsubtext}{Corollary}{4}{}
\(\oneBPNI \in \BP\cdot \NP\)\@.
\end{alabsubtext}
%
\apar{3-14}
Sch{\"o}ning~\cite{cj98-01-20} gives a direct proof 
that the graph isomorphism problem is in AM
(i.e., without using the relationship between IP and AM)
by using the Sipser hashing technique~\cite{cj98-01-23}\@.
We remark that 
we can modify Sch{\"o}ning's proof based on our technique,
and also directly obtain Corollary~4\@.
%
\apar{3-15}
Note that both classes, 
\(\BP\cdot \NP\) and \(\NP \cdot \co\RP\), can very loosely be considered
as some slight extensions of NP\@.
In this sense,
we have shown that \(\oneBPI\) is in a slight extension of \(\NP \cap \co\NP\)\@.
%
\begin{alabsubtext}{Corollary}{5}{}
\(\oneBPI \in \NP \cdot \co\RP ~\cap~ \BP\cdot \co\NP\)\@.
\end{alabsubtext}
%
\apar{3-16}
Boppana, H{\aa}stad, and Zachos~\cite{cj98-01-08} 
(see also Sch{\"o}ning~\cite{cj98-01-21})  
have shown that a \(\co\NP\)-complete set cannot be in \(\BP\cdot\NP\)
unless the polynomial hierarchy collapses to the second level,
in fact, even to \(\BP\cdot\NP\)\@.
Hence, we get the main result of this section\@.
%
\begin{alabsubtext}{Corollary}{6}{}
\(\oneBPI\) is not \(\NP\)-hard,
unless \(\PH = \Sigma^p_2\)\@.
\end{alabsubtext}
%
\apar{3-17}
Because ordered branching programs are a restricted form of
read-once branching programs, Corollary~6 can be applied\@.
The equivalence problem for ordered branching programs is in P~\cite{cj98-01-13}; therefore,
the isomorphism problem for ordered branching programs is in NP\@.
%
\begin{alabsubtext}{Corollary}{7}{}
The isomorphism problem for ordered branching programs is not \(\NP\)-complete
unless \(\PH = \Sigma^p_2\)\@.
\end{alabsubtext}
%
\apar{3-18}
Because computational models such as branching programs
work over inputs from \(\{0,1\}\), a set of size two,
Corollary~1 restricts our techniques
to multilinear polynomials\@.
However, if we start with polynomials of degree~\(d\) over \(\Q\)
for some constant~\(d > 0\),
then we can apply the above protocol for testing the
nonisomorphism of two such polynomials\@.
Just take the test domain \(T\) of size \(2dn\) for polynomials
with \(n\) variables\@.
For the representation of the polynomials it is enough that
we can evaluate them efficiently at any point\@.
Therefore,
the nonisomorphism problem for polynomials over \(\Q\) is in \(\BP \cdot \NP\)\@.
%
\begin{alabsubtext}{Corollary}{8}{}
The isomorphism problem for polynomials of degree~\(d\) over \(\Q\)
is not \(\NP\)-hard
unless \(\PH = \Sigma^p_2\)\@.
\end{alabsubtext}
%
\apar{3-19}
Our interactive proof system for \(\oneBPNI\) was motivated
by the one for \(\GNI\)\@.
However, 
it is more general now, in the sense that it
can be used to solve \(\GNI\) as a special case\@.
Specifically,
one can assign a polynomial to a graph
such that nonisomorphic graphs are mapped to nonisomorphic polynomials: e.g.,
let \(G = (V,E)\) be a graph, where \(V = \{1, \dots, n\}\)\@.
We take one variable \(x_i\) for each node \(i \in V\)\@.
Define
\begin{eqnarray*}
e_i(x_1, \dots, x_n) &=& x_i^2 \prod_{(i,j) \in E} x_j, \mbox{ and}\\
p_G(x_1, \dots, x_n) &=& \sum_{i=1}^n e_i(x_1, \dots, x_n)
\end{eqnarray*}
%
\apar{3-20}
For graphs \(G_0, G_1\) we have that
\(G_0 \iso G_1 \iff p_{G_0} \iso p_{G_1}\)\@.
Therefore, we again obtain the result about \(\GI\)
from Corollary~8\@.

\asection{4}{Extension to Arithmetic Circuits}
%
\apar{4-1}
In this section,
we extend the above protocol for branching programs
to an interactive proof
to decide the nonisomorphism of two arithmetic circuits
over a large enough field, \(\F\)\@.
We start with \(\F = \Q\)
for an infinite field of characteristic 0\@.
%
\apar{4-2}
Let~\(C_0\), \(C_1\) be two arithmetic circuits with \(n\) inputs that are of depth~\(d\)\@.
We take the protocol from the previous section and modify it
according to Corollary~3\@.
Let \(T = \{1, \dots, 2n2^d\}\) and \(M=\{1, \dots, 2^{2N}\}\), where \(N=nd\)\@.
%
\begin{description}
\item[V1:] 
The verifier starts by randomly choosing \(i \in \{0,1\}\) and a permutation~\(\varphi\)
as before,
and now \(6Nk\) points \(\Vector{r}_1, \dots, \Vector{r}_{6Nk} \in T^n\),
where \(k = \lceil n \log n \rceil +2\),
and for each point \(\Vector{r}_l\), a number \(m_l \in M\)\@.
Then the verifier 
computes \(y_l = p_{C_i} \circ \varphi (\Vector{r}_l) \bmod {m_l}\), for \(l = 1, \dots,6Nk\),
and sends the set of triples \(R = \set{(\Vector{r}_l,y_l,m_l)}{l = 1, \dots,6Nk}\)
to the prover\@.
\item[P1:]
The prover sends
\(j \in \{0,1\}\) and 
a  permutation~\(\varphi'\) to the verifier\@.
\item[V2:] 
If \(i=j\), then the verifier accepts\@.
If \(i \not= j\), the verifier
checks whether 
\(p_{C_j} \circ \varphi'\) matches the set \(R\), that is, whether
\(y_l = p_{C_i} \circ \varphi' (\Vector{r}_l) \bmod {m_l}\), for \(l = 1, \dots,6Nk\)\@.
If the test fails, the verifier rejects;
otherwise, it sends \(\varphi\) to the prover\@.
\item[P2:]
The prover sends
a point \(\Vector{r}' \in T^n\) and \(m' \in M\) to the verifier\@.
\item[V3:] 
Finally,
the verifier accepts if and only if
\(p_{C_i} \circ \varphi (\Vector{r}') \not\equiv p_{C_j} \circ \varphi' (\Vector{r}') \pmod{m'}\)\@.
\end{description}
%
\apar{4-3}
Combining the argument in the previous section with Corollary~3,
the verifier will accept two isomorphic arithmetic circuits
with probability at most \(3/4\)\@.
Note that the prover in step P2 must prove to the verifier that two numbers differ;
therefore, the computation modulo some number does not work in favor of the prover
in that case\@.
Two nonisomorphic arithmetic circuits
are still accepted with probability one\@.
%
\apar{4-4}
The case of infinite fields of characteristic greater than 0 is analogous\@.
As briefly explained in Section~2.4, the test domain 
becomes the polynomial ring \(\GF(q)[x]\) when the field has characteristic~\(q\)\@.
Computations are done modulo randomly chosen polynomials of small degree,
and can therefore be done in polynomial time\@.
%
\apar{4-5}
\begin{alabsubtext}{Theorem}{3}{}
The nonisomorphism problem for arithmetic circuits over infinite fields
is in \(\BP \cdot \NP\)\@.
\end{alabsubtext}
%
\apar{4-6}
If the  arithmetic circuits are over a finite field, say \(\GF(q)\),
where \(q\) is some prime power,
we run into the problem that there might not be enough elements
for our set~\(T\) to make the above protocol work\@.
Instead of \(\GF(q)\), we take  the extension field
\(\GF(q^t)\), where \(t\) is the smallest integer such that \(q^t \geq 2n2^d\),
so that \(t = \lceil \log_q 2n2^d \rceil\)\@.
Then we can set \(T = \GF(q^t)\)\@.
By Corollary~1,
when \(q > 2^d\),
we have that two polynomials over \(\GF(q)\) are equivalent
if and only if they are equivalent over any extension field\@.
%
\apar{4-7}
The verifier must be able to evaluate a polynomial  at a given point in
the extension field\@.
For this,
it needs an irreducible polynomial~\(\phi(x) \in \GF(q)[x]\)
of degree~\(t\)\@.
The verifier can cycle through all the \(q^{t+1} \leq 2n2^d q^2 < 2nq^3\)
polynomials in \(\GF(q)[x]\) of degree~\(t\), and check irreducibility
in polynomial time using the Berlekamp algorithm~(see \cite{cj98-01-06}, chapter 6),
and the verifier will find an irreducible polynomial  \(\phi(x)\)
in polynomial time\@.
Then \(\GF(q^t)\) is isomorphic to  \(\GF(q)[x]/\phi(x)\)\@.
Therefore,
knowing \(\phi(x)\), the verifier can do all computation needed
in polynomial time, and
the protocol can proceed as in the case of branching programs\@.
%
\begin{alabsubtext}{Theorem}{4}{}
The nonisomorphism problem for arithmetic circuits of depth~\(d\) 
over a finite field of size more than \(2^d\)
is in \(\BP \cdot \NP\)\@.
\end{alabsubtext}
%
\apar{4-8}
The lower bound on the field size is crucial:
for small fields, the equivalence problem for arithmetic circuits 
is coNP-complete~\cite{cj98-01-19}\@.

\asection{5}{Perfect Zero-Knowledge Interactive Proofs}
%
\apar{5-1}
Goldreich, Micali, and Wigderson~\cite{cj98-01-16} show that there are
perfect zero-knowledge interactive proofs for 
the graph isomorphism problem, GI, and its complement, GNI\@.
Adapting their ideas,
we show the existence of a perfect zero-knowledge interactive proof
for the isomorphism of branching programs or arithmetic circuits\@.
Fortnow~\cite{cj98-01-14} and Aiello and H{\aa}stad~\cite{cj98-01-02} have shown that
any set that has a perfect zero-knowledge interactive proof is in \(\AM \cap \co\AM\)\@.
Thus it follows again from
the result in this section that \(\oneBPI \in \co\AM\)\@.
%
\begin{alabsubtext}{Theorem}{5}{}
There is a perfect zero-knowledge interactive proof system for \(\oneBPI\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{5}{}
\prooffontshape
\apar{Proof of Theorem 5-1}
The IP protocol described below accepts \(\oneBPI\)
and has the perfect zero-knowledge property\@.
The  inputs are two read-once branching programs \(B_0\) and \(B_1\),
both over \(n\) variables\@.
Let \(T = \{1, \dots, 2n\}\)\@.
The following steps are repeated \(m\) times,
each time using independent random bits\@.
%
\begin{description}
\item[V1:] 
The verifier randomly picks 
points \(\Vector{r}_1, \dots, \Vector{r}_k \in T^n\),
where \(k = \lceil n \log n \rceil +2\),
and sends them to the prover\@.
\item[P1:]
The prover randomly chooses
a permutation~\(\varphi\)
and sends \(y_l = p_{B_0} \circ \varphi(\Vector{r}_l)\), for \(l = 1, \dots,k\),
to the verifier\@.
\item[V2:] 
The verifier randomly picks 
\(j \in \{0,1\}\) and sends it to the prover\@.
\item[P2:]
The prover sends a permutation~\(\pi\) to the verifier such that
\(p_{B_j} \circ \pi(\Vector{r}_l) = y_l\), for \(l = 1, \dots,k\)\@.
\item[V3:] 
Finally,
the verifier accepts if and only if
this latter condition regarding~\(\pi\) in fact holds\@.
\end{description}
%
\apar{Proof of Theorem 5-2}
By arguments similar to those in Section~3,
the above protocol constitutes  an interactive proof system for \(\oneBPI\):
if \(B_0 \iso B_1\) and the prover behaves as described in the protocol,
then the verifier will always accept\@.
If \(B_0 \not\iso B_1\),
then the verifier will accept with probability at most \(3/4\)
in each round,
no matter what the prover does,
and hence, with probability at most \((3/4)^m\)
after \(m\) rounds\@.
%
\apar{Proof of Theorem 5-3}
For the zero-knowledge property,
it is easy to see that the specific verifier in the protocol
gets no extra information\@.
The communication between \(P\) and \(V\) can be produced with equal distribution
by the following algorithm~\(M_V\):
randomly pick
\(j \in \{0,1\}\),
\(\Vector{r}_1, \dots, \Vector{r}_k \in T^n\),
and a permutation~\(\varphi\)
and output \(\Vector{r}_l\) and \(p_{B_j} \circ \varphi(\Vector{r}_l)\), for \(l = 1, \dots,k\),
and furthermore, \(j\) and \(\varphi\)\@.
%
\apar{Proof of Theorem 5-4}
By arguments similar to those in \cite{cj98-01-16},
one can show that \(P\) in fact conveys no knowledge
to any verifier, even verifiers that deviate from the above protocol\@.
We give a very short description so that a reader familiar with \cite{cj98-01-16}
can easily fill in the details\@.
%
\apar{Proof of Theorem 5-5}
Let \(V^*\) be an interactive machine\@.
We cannot simply define \(M_{V^*}\) the same way as for the specific verifier~\(V\) above,
because it has chosen \(j\) uniformly at random in step V2,
and therefore \(M_V\) could do the same thing\@.
However,
in general, \(V^*\) can make its choice of \(j\) dependent on the points
\(((\Vector{r}_1,y_1), \dots, (\Vector{r}_k,y_k))\) that it gets from the prover
after the first round\@.
On the other hand,
by only knowing \(j\) in advance, \(M_V\) could produce an isomorphism~\(\varphi\)
as above\@.
%
\apar{Proof of Theorem 5-6}
The way \(M_{V^*}\) works is as follows\@.
The \(M_{V^*}\) algorithm starts by simulating \(V^*\) to produce the points \(\Vector{r}_1, \dots, \Vector{r}_k \in T^n\)\@.
Then \(M_{V^*}\) randomly picks
\(j \in \{0,1\}\), and a permutation~\(\varphi\)\@.
This is similar to \(M_V\) above,
except that \(j\) is now considered only as a candidate for the value 
that will actually be produced by \(V^*\)\@.
Next, \(M_{V^*}\) simulates \(V^*\) when \(V^*\)
gets the points \((\Vector{r}_1,y_1), \dots, (\Vector{r}_k,y_k)\) from the prover,
thereby obtaining the value \(j_{V^*}\) that \(V^*\) will send to the prover
after the first round\@.
Then,
in case that \(j = j_{V^*}\),
\(M_{V^*}\) is ``lucky,'' and can make the same output as \(M_V\) above, namely,
\(\Vector{r}_l\) and \(p_{B_j} \circ \varphi(\Vector{r}_l)\), for \(l = 1, \dots,k\),
and \(j\) and \(\varphi\)\@.
If \(j \not= j_{V^*}\),
then \(\varphi\) is the wrong permutation, and \(M_{V^*}\) cannot make a legal output\@.
Instead,
\(M_{V^*}\) repeats this whole process until it gets lucky, i.e., until \(j = j_{V^*}\),
and then makes an output\@.
%
\apar{Proof of Theorem 5-7}
The probability that \(M_{V^*}\) is lucky is \(1/2\)\@.
Therefore we expect \(M_{V^*}\) to repeat this process twice;
hence, \(M_{V^*}\) runs in expected polynomial time\@.
%
\apar{Proof of Theorem 5-8}
Finally,
the output distribution of \(M_{V^*}\) is identical
to that of the conversation of \(P\) and \(V^*\)\@.
Intuitively this is clear, because roughly speaking,
\(M_{V^*}\) simply waits until it can do the same trick
as \(M_V\) from above\@.
Therefore,
the output of \(M_{V^*}\) might be delayed,
but has the same distribution\@.
There are some subtleties that one must take care of,
but a formal argument can then easily be adapted from \cite{cj98-01-16}\@.
Note also that in fact \(M_{V^*}\) must produce the conversation
of several rounds of the protocol\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 5}}
\end{alabsubtext}
%
\apar{5-2}
Clearly, Theorem~5 extends 
to the isomorphism problem for arithmetic circuits\@. 
%
\apar{5-3}
The interactive proof for \(\oneBPNI\) presented in Section~3
might not be zero knowledge, because in the first step
the verifier can present points to the prover that are obtained
in a different way than by random guesses, 
and the answers from the prover later on might give some
extra information to the verifier\@.
For the graph-nonisomorphism problem \(\GNI\),
this problem is solved by 
letting the verifier ``prove to the prover''
that it has a permutation in hand that was used to produce the
graph sent to the prover~\cite{cj98-01-16}\@.
However,
there are some problems in adapting this method to \(\oneBPNI\)
that arise from the way we describe polynomials in the interactive proofs,
namely, as a set of points\@.
We leave it as an open problem to show
that \(\oneBPNI\) has a zero-knowledge interactive proof\@.

\asection{Acknowledgments}{}
%
We thank Manindra Agrawal for many enjoyable discussions\@.
In particular,
the observation that the isomorphism problem for polynomials 
is more general than the one for graphs (see end of Section~3)
is due to him\@.
Thanks also go to
Bernd Borchert, Lance Fortnow, and Uwe Sch{\"o}ning 
for very helpful comments\@.
%
\end{articletext}
%
\bibliography{thierauf}
\bibliographystyle{alpha}
%
\end{document}