



%SERCIO QUETSA E' LA VERSIONE DEFINITIVA DI AVERAGE DEL 19/5 PER PHYCOMP94



 \documentstyle[11pt]{article}
%\input articleHeader


	\newcounter{esempi}[section]
	\newcounter{ics}

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{fact}{Fact}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{note}{Note}[section]

\newcommand{\esempio}{\addtocounter{esempi}{1} 
					  \noindent {\bf Example \thesection .
\theesempi\ }}

\newcommand{\eproof}{\hfill$\Box$  \medskip} 
\newcommand{\sketchofproof}{\noindent {\em Sketch of 
the proof}.~ }
\newcommand{\proof}{\noindent {\em Proof}.~}

\newcommand{\fmod}[1]{\mbox{$\mid \! \! #1 \! \! \mid $}}
				%da non usare in pedice ed apice!!
 

			
%%
%% An environment for formatting programs. 
%%
%       written by Hal Perkins
%       adapted by Charles Elkan        9/3/86
%       keyword macros by Anne Neirynck
%
% Usage :
%
% \begin{program}
% program text\\
% program text
% \end{program}
%
% The program environment is a tabbing environment with ten tab 
%stops spaced
% evenly from the left of the page.  Initially the left
% margin is the second
% tab stop.  Use \+ to indent following lines one more 
%tab stop, \- to undo
% the effect of \+, and \> at the beginning of a line to indent 
%%an extra tab.
 
\newlength{\pgmtab}        
  % \pgmtab is the width of each tab in the
\setlength{\pgmtab}{2em}   
  %  program environment
 
\newenvironment{program}{\begin{tabbing}
\hspace{0em}\=\hspace{0em}\=%
\hspace{\pgmtab}\=\hspace{\pgmtab}\=\hspace{\pgmtab}
\=\hspace{\pgmtab}\=%
\hspace{\pgmtab}\=\hspace{\pgmtab}\=\hspace{\pgmtab}
\=\hspace{\pgmtab}\=%
\+\+\kill}{\end{tabbing}}
 
% The following commands should be used OUTSIDE math mode
 
%\newcommand {\ABORT}{{\bf abort\ }}
%\newcommand {\AND}{\mbox{\bf and\ }}
%\newcommand {\ASSIGN}{\mbox{~:=~}}
%\newcommand {\BEGIN}{{\bf begin\ }}
%\newcommand {\DIV}{{\bf div\ }}
%\newcommand {\DO}{{\bf do\ }}
%\newcommand {\DOWNTO}{{\bf down to\ }}
%\newcommand {\ELSE}{{\bf else\ }}
%\newcommand {\ELSEIF}{{\bf else\ if\ }}
%\newcommand {\END}{{\bf end}}
%\newcommand {\FALSE}{{\bf false}}
%\newcommand {\FOR}{{\bf for\ }}
%\newcommand {\FOREVER}{{\bf forever\ }}
%\newcommand {\FOREACH}{{\bf for each\ }}
%\newcommand {\FUNCTION}{{\bf function\ }}
%\newcommand {\GOTO}{{\bf go to\ }}
%\newcommand {\GUESS}{{\bf guess\ }}
%\newcommand {\IF}{{\bf if\ }}
%\newcommand {\IN}{{\bf in\ }}
%\newcommand {\LET}{{\bf let\ }}
%\newcommand {\LOOP}{{\bf loop\ }}
%\newcommand {\NOT}{\mbox{\bf not\ }}
%\newcommand {\OR}{\mbox{\bf or\ }}
%\newcommand {\PARBEGIN}{\mbox{\bf parbegin\ }}
%\newcommand {\PAREND}{\mbox{\bf parend}}
%\newcommand {\PRINT}{\mbox{\bf print\ }}
%\newcommand {\PROGRAM}{{\bf program\ }}
%%\newcommand {\PROCEDURE}{{\bf procedure\ }}
%\newcommand {\RANDOM}{\mbox{\bf random}}
%\newcommand {\RECEIVE}{\mbox{\bf receive\ }}
%\newcommand {\REPEAT}{\mbox{\bf repeat\ }}
%\newcommand {\RETURN}{{\bf return\ }}
%\newcommand {\SKIP}{{\bf skip\ }}
%\newcommand {\THEN}{{\bf then\ }}
%\newcommand {\TIME}{\mbox{\bf time\ }}
%\newcommand {\TO}{{\bf to\ }}
%\newcommand {\TRANSMIT}{{\bf transmit\ }}
%\newcommand {\TRUE}{{\bf true}}
%\newcommand {\UNTIL}{\mbox{\bf until\ }}
%\newcommand {\WHILE}{{\bf while\ }}
 
\newcommand {\proofend}{{\bf \large $\Box$}}

\setlength{\textwidth}{17.2cm}
\setlength{\oddsidemargin}{-0.7cm}
\setlength{\topmargin}{-1.6cm}
\setlength{\textheight}{23.6cm}
\setlength{\columnsep}{1cm}
%\setlenght{\hoffset}{-1cm}
%\pagestyle{empty}

%\pagestyle{empty}
\begin{document}
\title{ On the average-case complexity of the reversibilty problem for
finite cellular automata}
\author{Andrea CLEMENTI\\
 Department of Computer Science\\ 
 University of Roma "La Sapienza" \\   Italy - Email: clementi@sci.uniroma1.it
\and
Pierluigi PIERINI \\ Laboratory for Computer Science \\ Massachusetts Institute of Technology
 \\ Cambridge, MA USA - E-mail: pp@im.lcs.mit.edu
\and
  Russell  IMPAGLIAZZO
\\
  Department of Computer Science, University of  California, 
   San Diego\\  California USA - E-mail: Russell@cs.ucsd.edu}

\date{}
\maketitle 

%\medskip
 \begin{center}
{\bf (Extended Abstract)}
\end{center} 

\medskip
\noindent
{\bf Keywords:} Cellular Automata; invertibility; average-case   complexity of computational problems.

\section{ Introduction }


There is a renewal of interest in studying the fundamental connections 
between physics and computation \cite{[BGLVZ93],[BP93],[JaSo 90]} 
and, in particular, in modelling computing systems which explicitly 
consider the fundamental physical limitations such as finiteness of the 
speed of light and layout in ordinary space. 
  Cellular automata represent one of the best mathematical model under this point of
view \cite{[BP93],[ToMa90]}.
 Cellular automata are 
networks of 
numerable, identical and uniformly interconnected machines ({\em cells\/}) evolving in a parallel, synchronous way. Hence, the local interactions among the cells determine a 
{\em global function} acting on the space of all possible configurations.
A cellular automaton is {\em invertible} if its global function is bijective.
 The  invertibility  of a cellular automaton is an important issue in modelling reversible physical phenomena.

 Kari \cite{[Ja 90]} has recently proved that the problem which consists of deciding whether  or not a given 
 cellular automaton is invertible  (in short REV) is undecidable.
Most of   cellular automaton 
applications in 
computer science requires to consider a finite number 
of machines rather than an infinite one. In \cite{[CP 92]},
 the  complement problem of  REV, for finite cellular automata, has been proved to be
  $NP$-complete. The proof given in \cite{[CP 92]} holds also
 under very strong restrictions on the topology ({\em neighborhood\/}) 
 of the connections among cells;  more recently, a different proof of this result has appeared in 
\cite{[MR 93]}.
   The consequences
 of these results 
 for computer science and physics are also analysed in \cite{[C 94],[APP 94]}.
 
In this paper, 
 we  investigate the average-case   complexity (see \cite{[Le86], [Gu91]}) of a natural 
  generalization     of 
 REV. In this  new version, the instance specifies also the particular 
{\em closed} subset of global configurations on which the invertibility property is
 required.    When an $NP$-completeness  result arises, the attention
naturally focuses on less ambitious goals than to decide $any$
 instance of the problem in polynomial time. 
 Several $NP$-complete decision problems have algorithms working in  polynomial
 average-time according to a fixed probability function given on the input space \cite{[DF 89],[K 77]}
(that is they belong to the complexity class $AP$ - see section \ref{defi}).
 However,
 we   show  that  polynomial average-time algorithms for our problem are unlikely to exist. 
 Indeed,     we  
prove that the generalized   version of  REV   cannot belong to   $AP$ unless $RNP$, the randomized version of the class $NP$, 
  is  contained in $AP$ (i.e.  all $NP$-complete problems would have an algorithm working efficiently in average). To do this, we show that our  problem  is   {\em complete}
 for the complement class of $RNP$ (i.e. Co$RNP$).  
Very few examples of interesting  complete problems have  been found until now for this class.
 The  average-case complexity
 of any computational problem depends not only
 on the problem but on the probability function as well. 
In particular,  the probability function
 yielding the uniform distribution on the input of a given size, is often uninteresting from the point of view of practical applications: in most cases, we could prefer to give more ``importance'' to a fixed subset  of inputs rather than another. 
Following  this  line of reasoning,  
 it is
 interesting to underline that our  hardness  result holds for $every$ choice of the
 positive probability function given 
on the space of all finite cellular automata.

Finally,  
we shall discuss some consequences of this 
 result in  the theory and applications of cellular automata.





 
   

\section{Preliminaries}\label{defi}
 
\noindent
{\bf Finite cellular automata.} 
A finite two-dimensional 
cellular automata (in short  $ ca$) can be formally defined  as a fourtuple
$A=(n,Q,N,f)$ where:
 
 \begin{itemize}
 
\item   $n$ is the size of the 
support array; hence, there are $n^2$ finite-state 
automata (called {\em cells\/}) located 
on the  two-dimensional lattice  having periodic structure (i.e. ${\cal 
Z}^2_n$); 

\item
  $Q$ is the finite set of cell states;
 
 \item
  $N$ is the set of   ${\cal Z}^2_n$-vectors determining 
the $neighborhood$; for any  $j\in N$, the 
cell at position $i+j$ is a 
$neighbor$ of cell at position $i$ (in 
which follows we shall identify the cell with its position); 
The set of neighbors of $i$ is denoted as $N(i)$. The {\em 
Moore} neighborhood, 
 consisting of the center cell and the eight surrounding 
cells, is called   $N^m$.

\item
  $f: Q^{|N|} \rightarrow Q$ is the local    function; the     
state of each cell $i$ is updated 
according to  $f$ which has    the   state of the neighbors of $i$ as input.

\end{itemize}

 

A configuration of $A$ is a function $X:{{\cal 
Z}^2_n} \rightarrow Q$ (i.e. an element of the set $\Sigma = Q^{{\cal 
Z}^2_n}$) and since the evolution of the system is synchronous (i.e. there is a global, discrete
clock which is valid for all the cells) the {\em 
local 
map\/} consisting of the pair $(N,f)$ uniquely determines a global 
function $F: \Sigma \rightarrow \Sigma$. 

\medskip
\noindent
{\bf Average-case complexity.}
 Let us now  revise the basic definitions of   Levin's
theory  of the  average-case complexity \cite{[Le86]}.  All   
definitions 
and results given below can be found,  
 in a more detailed form,  in \cite{[Gu91]}.
A {\em randomized} decision problem is a pair $(L,Pr)$ where $L$ is a
decision problem on the instance set $S^*$ (i.e. a subset of $S^*$) and $Pr$ is a probability 
function on $S^*$. We   call $(L/X,Pr_{/X})$ the  restriction of 
$(L,Pr)$ to
a subset $X$ of $S^*$ with $Pr(X) >0$   ($Pr_{/X}$ is the probability function
proportional to $Pr$ in $X$ and zero outside).
Given a function  $f:S^*\rightarrow R^+$, then
 $f$ is polynomial on $Pr$-average if there exists an 
$\epsilon>0$ such
that:
%\begin{equation}
$${\Sigma}_{\{x:|x|>0\}}(f(x))^{\epsilon}\cdot {|x|}^{-1} \cdot Pr(x) < \infty.$$  
%\label{Ia}
%\end{equation}

 %\begin{lemma} 
%Let us assume that there exists a polynomial $p$ such that
 %for every $n$ either $Pr(H_n) \geq {1/(p(n))}$ or  $Pr(H_n)=0$; then
%the condition \ref{Ia} is equivalent to the following. There exists $q >0$
%such that:

%\begin{equation}
%{\Sigma}_{|x|>0}(f(x))^{1/q}\cdot {|x|}^{-1} \cdot Pr(x)<\infty \label{1a}
%\end{equation}
%
%We call   $q$ the witness of the  polynomiality  of $f$ on  $Pr$-average.
%\end{lemma}

%\begin{definition}

Now, we can introduce the following definitions:

\begin{itemize} 

\item A randomized decision problem $(L,Pr)$ is in  $AP$  if
 there is a Turing machine deciding $L$ within 
 time polynomial on $Pr$-average.
Similarly, a function $f:S^*\rightarrow {S'}^*$ is computable in $AP-time$
with respect to the  probability function $Pr$ on $S^*$ if there is 
a Turing machine which computes $f$ within time polynomial
 on $Pr$-average.

\item Let $Pr_1$ and $Pr_2$ be two probability functions on $S^*$;  $Pr_2$
{\em dominates} $Pr_1$ if there exists a polynomially bounded 
function $f:S^*\rightarrow R^+$ such that, for any $x\in S^*$, we have:
 $Pr_1(x)\leq f(x)Pr_2(x)$.
Then, a  randomized decision  problem  $(L,Pr)$ is in  $RNP$ if $L$ is 
in $NP$ and $Pr$  is dominated by a probability function
$Pr_2$ whose  distribution $Pr_2^*(y) = {\Sigma}_{x<y}Pr(x)$ is 
polynomial-time 
computable.
\end{itemize}
%\end{definition}

A function f {\em reduces} a decision problem
$L_1$ to another $L_2$ if, for any instance $x$ of $L_1$, we have $x\in 
L_1$
iff if $f(x)\in L_2$. Moreover, a function $f:S^*_1 \rightarrow S^*_2$ {\em transforms} 
$Pr_1$ into $Pr_2$ if, for any 
$y \in S_2^*$,  $Pr_2(y)=\Sigma_{\{x:f(x)=y\}}Pr_1(x)$.
 Thus, we  
say that 
 $Pr_1$ is dominated by $Pr_2$ with  respect to
a function $f$  (in symbols $Pr_1 {\leq}^f Pr_2$)  iff there exists a probability function 
 $Pr$
 such that  $Pr$ dominates  $Pr_1$
and $f$ transforms $Pr$ into a restriction of $Pr_2$.
 For any pair of randomized problem $(L_1,Pr_1)$, $(L_2,Pr_2)$ we say that 
a polynomial-time  function $f$ {\em
Av-reduces} $(L_1,Pr_1)$ into $(L_2,Pr_2)$ iff  it reduces 
$L_1/\{x:Pr_1(x)>0\}$ to $L_2$
and  $Pr_1 {\leq}^f Pr_2$. 
 This  definition extends the concept of reduction among decision problems
 from $NP$ to $RNP$;
 indeed, it is possible to prove that the Av-reducibility   is a transitive  relation in $RNP$. Moreover,  
if  $(L_1,Pr_1)$ Av-reduces to $(L_2,Pr_2)$ and  $(L_2,Pr_2)$
is in  $AP$ then $(L_1,Pr_1)$ is in $AP$; in particular any restriction
of an $AP$ problem is in $AP$.
Finally, we say that a randomized decision problem  $(L,Pr)$ is $RNP-complete$ if
it is in $RNP$ and for any  $(L_1,Pr_1)\in RNP$, $(L_1,Pr_1)$
Av-reduces to  $(L,Pr)$.
In which follows we   present a randomized problem that Levin 
\cite{[Le86]}
 and, more recently,  Gurevich
\cite{[Gu91]} proved to be complete for    $RNP$.  

\medskip

 Given a finite
 set of $colors$  $C$ we call     {\em set of tiles\/}  any subset $\tau 
\subseteq 
C^4$ where each $t \in \tau$ represents a $1 \times 1$ square with colored 
edges. The four edge colors of a fixed tile $t$ will be denoted 
as: $top(t)$, $right(t)$, $bottom(t)$ and  $left(t)$.
  Moreover, given a finite
 set of tiles  $\tau$, a function 
$ r:[ 0,\ldots,j-1 ] \rightarrow \tau $ is a $\tau-row$  of
length $j$ if $left(r(i+1)) = right(r(i))$ for  any $i<j$.

\medskip
\noindent
{\em  Randomized bounded Tiling Problem}  {\bf 
(RTP$(\tau,n,r)$)}\footnote{Observe 
the ``generalization'' represented by
 string $r$ with respect to the classical definition of the Tiling Problem in which no
strings are determined (see
 \cite{[GaJo79]}).}
\underline{Instance:} A finite set of tiles $\tau$, the unary notation 
 for an   
 integer $n>1$, an  integer $j$ such that $0<j<n$ and a $\tau$-row $r$ of   
length $k$. $r$ is  such that either $k=j$ or   $k<j$ and $\tau$ has no tiles 
$t$ having $left(t) = right(r(k))$. 
  \underline{Question}: Does a correct $\tau$-tiling of the square 
$T = [0,\ldots,n-1]\times [0,\ldots,n-1]$ exist?  (for  a 
correct
 $\tau$-tiling we intend  a function
$g:T \rightarrow \tau$ 
 such that the common  edge of every pair of adjacent tiles has the same
color and  with $g(0,i)=r(i)$ for any $i<k$; the tiles cannot be rotated).
\underline{Probability:} Choose $\tau$ with any fixed positive 
probability function;
choose $n$ with the ``standard'' probability\footnote{See section 2 of \cite{[Gu91]}, for more discussions on appropriate probability functions on the set of positive integers;} proportional to $1/n^2$; 
choose uniformly
$j<n$ (i.e. with probability $1/n$); choose uniformly $r(o)$; choose 
$r(i+1)$ 
uniformly in the
set ${\tau}_i=\{t\in \tau $ : $ left(t)=right(r(i))\}$, $i=1, \ldots, k-2$.   
All these choices
are mutually  independent, thus  the resulting probability of an $RTP$-instance is the product of the probabilities of the single events described above. 

%\begin{theorem}  \label{Pow}
%$RS(M,w,n)$ is complete for $RNP$. It remains  complete even when we 
%restrict
%$n$ to be in the  subset $H_c=\{2^h-c: \: h>1 \}$, for any fixed 
%$c\in\{0,1,2\}$.

%\end{theorem}



%\noindent {\bf Remark.} The second part of the above theorem is a direct 
%consequence of
%the proof given in \cite{[Gu91]}.

\medskip

\begin{theorem} \label{1.3}
{\em \cite{[Le86],[Gu91]}}
  $RTP(\tau,n,r)$ is
$RNP$-complete. 

\end{theorem}  

In the following corollary, we   summarize a  property which is a direct consequence  of
 the proof of theorem \ref{1.3} (see theorem B1 and lemma B6 of appendix B in 
 \cite{[Gu91]}); such a property  will be used for proving our result.


\begin{corollary}       \label{CSU}

%If $(M,w,n)$ is an $RS$ instance with $w \in \{0,1\}^k$ 
%$w=(w_0,\ldots,w_{k-1})$,
 %then   $f(M,w,n)$
%is an  $RTP$ instance $({\tau}^A,n,r)$ where ${\tau}^A$ is  
%uniquely determined by the NTM $M$; the corresponding ${\tau}^A$-row $r$ 
%has 
%length $k$; moreover, $top(r(0))= (p,w_0)$ (where $p$ is the initial state 
%of $M$)
%and for $i=1,\ldots,k-1$ $top(r(i))= w_i$. 

$RTP$ remains $RNP$-complete even when,  for $i=1,\ldots,k-1$,
 $top(r(i)) \in \{0,1\}$ and  the size of 
 ${\tau}_i$,     $i=0,\ldots,k-2$, 
is exactly two, that is, when  the probability 
of any possible   $\tau$-row $r$ of length $k$    is proportional to ${(1/2)}^k$.

\end{corollary}

  \medskip
\noindent
{\bf The problem.}
A  $ ca$ is {\em invertible\/} if its global function is bijective. 
Thus, the invertibility problem (REV) consists of 
   deciding whether or not  a given $ca$ is 
invertible.
   We   define now the 
 generalization of REV`s complement problem,
since, for proving our result, we will always refer to this problem.
 However, since the class $AP$ is equal to its complement, 
it should be clear that  any  hardness  result
 (like an  $RNP$-completeness one) 
for one of the two   problems (i.e. REV and its complement)
    implies an equivalent  hardness result (i.e. Co$RNP$-completeness)
 for the other as well.   Since the set $\Sigma$ is finite,   the invertibility property is equivalent to the injectivity one, hence  
 REV `s complement (in short NIP)   consist of
 deciding the existence of a pair of
different configurations having the same image according to the  $ ca$ global function.
  Let us consider  the concept of  
  {\em legal} configurations which has been first  introduced 
for other decision problems dealing with  $ ca$ (see for example \cite{[Gr 87],
[Su89]}).  Consider  a subset\footnote{We remark that it is not a restriction  to consider subsets, like $P$,
 having always $(0,0)$ as the first element since the toroidal structure of the support.} 
$P = (P_1=\{0,\ldots,k_1\} \times P_2=\{0,\ldots,k_2\}) \subset  {\cal 
Z}^2_n $, 
  the restriction of any configuration $X \in \Sigma$, on the domain $P$, will be denoted as $X_{/P}$. Now, given any {\em pattern} $x$ for $P$ (i.e. $x:P \rightarrow Q$),
 we can introduce the following legal configuration set:
$$ \Sigma (P,x) = \{ X \in \Sigma \  \ : \ \  X_{/P} = x \}. $$

  When $P$ is  equal to the empty set, 
we shall adopt the convention: $\Sigma (\emptyset, \ast) = \Sigma$.
Moreover we say that $\Sigma (P,x)$ is {\em closed} with respect to
 the  $ca$  global function $F$ if, given any 
$X \in \Sigma$,
$  X \in \Sigma (P,x)$   iff $F(X) \in \Sigma (P,x) $.
 Finally, when the state set $Q$ consists of more than one component, we can easily adapt 
the above definitions:
without loss of generality, suppose $Q=Q_a \times Q_b$, then by using the previous notations, 
given any $P \subset {\cal Z}^2_n$ and any $Q_a$-pattern $x$ for $P$, that is any $x:P \rightarrow Q_a$,
we have the following configuration set:

 $$ \Sigma (P,Q_a,x) = \{ X \in \Sigma \  \ : \ \  X_{/P} = x \  \mbox{ with respect to 
 the  component }
 \ Q_a \}. $$

We are now ready to introduce the formal definition of our problem:


\medskip
 \noindent
 {\em  Randomized Non Invertibility Problem } {\bf  (RNIP$(A,P,Q_a,x)$)}   
  \underline{Instance}: A $ ca$ $A=(n,Q,N,f)$  with
 global function $F$, a support subset  $P= P_1 \times P_2 \subset {\cal Z}^2_n$ and a $Q_a$-pattern\footnote{In order to keep this definition as general as possible, the set $Q_a$ can be  either
 a subset of Q or a subset of a component of $Q$. In other words, the particular choice of $Q_a$, among these possibilities, has no relevance for our next 
result. }
 $x:P \rightarrow Q_a$. 
 \underline {Question}: Does two different configurations $X$ and
$Y$ belonging to the legal set $\Sigma (P,Q_a,x)$, such that $F(X)=F(Y)$, exist?
 \underline {Probability}: choose the $ ca$-size $n$ with the standard probability $Pr(n)$ 
proportional to $ 1/n^2$;
 choose $(Q,N,f)$ and $Q_a$ with your {\em favorite} positive probability
 function; choose the size of $P_1$ and $P_2$, independently,   with uniform distribution
 in the set $\{0, \ldots, n-1\}$;   choose a $Q_a$-pattern  $x:P \rightarrow Q_a$
 with uniform probability in the set $Q_a^P$ of all possible $Q_a$-pattern of $P$ (i.e. every possible pattern has probability $1/|Q_a^P|$). 
All these choices
are mutually  independent, thus the resulting probability of an $RNIP$-instance is the product of the probabilities of the single events described above. 

\medskip

 
Let us observe that the above definition contains the classical definiton of NIP as the particular case in which  
 $P=\emptyset$.

\section{The result}

Let us now give the result of this paper:

\begin{theorem}
 $RNIP$ is $RNP$-complete for any positive probability function given on the space of finite ca. Hence, the generalized version of $REV$ on finite ca, cannot be solved in polynomial time in the average-case,
unless $RNP=AP$.
\end{theorem}

 

\proof  (Overall Scheme). {\small In order to prove the theorem, we   show that     RTP Av-reduces to RNIP.   Let $z=\langle \tau,n,r \rangle$ (where the $\tau$-row $r$ has size $k$) 
be a given instance of RTP and let $TOP(r) \subseteq C^4$  be the subset of colors appearing in the Top-component of the tiles in $r$. Basically, the reduction   consists of the following three steps (which will be formally described in the full version of this paper - see also \cite{[C 94]}).

\begin{description}

\item[{\bf i)}] We first transform  $z=\langle \tau,n,r \rangle$  to a new instance  
$z^t=\langle {\tau}^t,n +1,r^t \rangle$, where $|{\tau}^t_i| = |{\tau}_i|$ for any
 $i=1,\ldots ,k-1$ (see definition of RTP), such that $\tau$ admits a correct tiling for 
the lattice ${\{0,\ldots,n-1\}}^2$ iff ${\tau}^t$ admits a correct tiling for
 the torus  ${\cal Z}^2_{n+1}$. Furthermore, we prove that this transformation is an Av-reduction\footnote{This first step shows also an independent result: RTP is RNP-complete also when the lattice has periodic structure} and thus, we can apply the following step.


\item[{\bf ii)}] We transform the instance $z^t$ to a particular $ ca$ 
$A=(n+1,{\tau}^t \times Q^A,N^m,f^A)$ having the following properties:

\begin{enumerate}

\item The size of set ${\tau}^t \times Q^A$ does not depend on $n$;

 
\item $f^A$ is the identity with respect to the component ${\tau}^t$, that is, it doesn`t
change the  tile component; 


\item A is not injective in  $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),
x(r)=\langle top(r^t(0)),
top( r^t(1)), \ldots, top(r^t(k-1)) \rangle$;

\item
 In  each pair of different configurations $X$ and $Y$ belonging to  
 $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$
 such that $F^A(X) = F^A(Y)$, there are no cell having the same value in both $X$ and $Y$.

\end{enumerate}

\item[{\bf iii)}] Finally, we transform  the  $ca$ $A$ defined in the previous step
to a new  $ ca$ $B=(n+1,{\tau}^t \times Q^A,N^m,f^B)$ where, for every cell $i\in {\cal Z}^2_{n+1}$, we have:

\[ f^B = \left\{ \begin{array}{ll}
f^A &   \mbox{ if there are no tiling errors in N(i)}  \\
  
 Identity \: function &  \mbox{ otherwise} \end{array} 
\right.\]



\end{description}

Let us now  give the proof scheme of  the correctness of the  above global reduction that  will be called $\pi$. 
In particular, 
$\pi$ maps each instance $z^t=\langle {\tau}^t,n +1,r^t \rangle$ to the RNIP-instance
 $\langle B, P=(\{0,\ldots,k-1 \} \times \{0\},
Q_a=TOP(r),x(r))\rangle$.
If the torus  ${\cal Z}^2_{n+1}$ can be correctly tiled with  tiles in ${\tau}^t$ 
then $B$ is 
not injective in $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$; indeed,  if we choose
 the ${\tau}^t$-component of two  different 
configuration
$X$ and $Y$ in order to have  the same correct tiling of the torus,
then  $f^B$ operate like $f^A$ for all the support cells.
 Since $A$ is not injective in $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$ (see property
 3. of $A$),  the $Q^A$-component of $X$ and $Y$ can be chosen\footnote{We observe that any configuration for $A$ can be also  seen   as a configuration of $B$ and viceversa} to form two different  
configurations of $B$ having the same image with respect to the global 
function of $B$ (in short $F^B$).
Conversely, if $B$ is not injective in 
$\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$ then we have 
$F^B (X)=F^B (Y)$, for some $X \neq Y$ belonging to this set and, moreover,  the 
  tile components of
$X$ and $Y$ must be the same (because of property 2. of $A$);
therefore, with  regard to the state component $Q^A$, we still have two different 
configurations $X$ and $Y$, belonging to $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$, having the same image also  according to  $F^A$.
From     property 4. of $A$, the local function $f^A$ must change the 
state of  every cell in $X$ or in  $Y$; same claim must hold for $f^B$,  thus, according with the definition of 
$f^B$, there must be  no tiling errors in the neighborhood of each cell
and the torus can be correctly tiled.
 
From step ii) of the above proof, it should be clear that in order to prove our result we have to define the  $ ca$ $A$ having  the properties 1.,..,4.
 This $ ca$ is crucial  
 since   represents the bridge from the definition of a particular 
local map to the expected  macroscopic behaviour. Let us now  give an informal description
of $A$. 
The set $Q^A$  has two components: a {\em tile\/} component (again!)
  and a finite set of boolean 
variables (i.e. an array of bits).  The tile component determines one or more   {\em 
passages} between adjacent cells (see also \cite{[APP 94],[Ja 90]}). When   a global configuration defines a correct tiling (with respect to  the tile component),  we have the following {\em covering} property:
the  passages   yield a {\em path}
 covering   all   cells of the 
toroidal support. A boolean variable 
(i.e. a bit) 
is defined on each   passage. In case of correct tiling of the 
neighborhood (with respect 
to the tile component),  the local function $f^A$ will operate the $XOR$ function 
between the bits of
consecutive passages in the path. A similar construction has been first introduced by Kari in 
\cite{[Ja 90]}, however his method (and, in particular, the  set of tiles adopted by him)
 works on  non periodic configurations of the infinite lattice. Under this point of view, our main technical result consists in making the path able to recognize the finite structure of the
toroidal support of arbitrary size by using only ``local'' informations.  To do this, we   
introduce a new  set of tiles  having the         {\em covering property}; moreover,
the cardinality of this   tile set
  doesn't   depend
 on the size of the toroidal support.

Finally, we observe that the set $\Sigma (\{0,\ldots,k-1 \} \times \{0\},TOP(r),x(r))$ is a closed set
with respect to both   $ca$ global functions $F^A$ and $F^B$ since 
they keep unchanged the component
${\tau}^t$; this   proves that RNIP is $RNP$-complete even  when we consider only closed subsets
 of $\Sigma$.

\medskip
\noindent
{\bf Probability function property}.  Let us now prove that $\pi$ is an 
Av-reduction. From  corollary \ref{CSU} and step i) of the reduction $\pi$, we can consider only 
RTP instances in which the set of the top colors of all possible 
${\tau}^t$-rows
 is $TOP(r^t)=\{0,1\}$
and     the corresponding probability 
of a given ${\tau}^t$-row $r^t$ of length $k$ $(0 \leq k <n)$ 
is proportional to ${(1/2)}^k$.  Thus, the 
probability of the RTP instance $z^t$ is  $Pr_1(z^t)=c(1/n^3)(1/2)^k$
 for some positive constant   
 $c$ depending only on $\tau$.  
Since  the 
subset $TOP(r)$
has always cardinality two, the probability of the  RNIP instance $w=\pi 
(z^t)$,  is 
$Pr_2(w)=\beta(1/n^3)(1/2^k)$ where $\beta$ is a positive constant  not 
depending on $n$ (remark also   property 1. of the   $ ca$ $A$). For these reasons, it 
is easy   
to verify that 
$Pr_2$ {\em dominates\/} $Pr_1$ with respect to $\pi$. \par}

 \section{Conclusions and future applications} \label{conclusion}

In this paper, we have presented  the first example of decision problem, dealing 
with cellular automata, which can be considered ``hard'' also  in the 
average-case complexity.
In (\cite{[Wo 85]}) a number of
 open problems concerning cellular automata were posed. One of them is 
the question of how common 
 ``hardness'' results are in problems dealing with cellular automata.
  The answer may have a significant bearing
on the  practical ability to predict the outcome of various chaotic
phenomena based on computation. In addition, some
of the practical difficulties of efficiently programming parallel 
computers might be revealed \cite{[WW86]}.
In particular,  our ``hardness'' result for REV implies
that, in order to obtain  a general-purpose computing model based on  
invertible  finite 
cellular automata, we should define   a    local map together with a closed 
subset of legal configurations which  {\em a 
priori\/} 
yield a global invertible process, since this  property cannot be, 
in general, efficiently 
tested  (i.e. in polynomial average-time). 

On the other hand, the $NP$-completeness result proved in \cite{[CP 92]}
  implies the existence of  a family  
of invertible finite ca having local and simple interactions  whose    inverse   maps have, on the contrary,
  large and complex 
interactions. This theoretical result,
 concerning the worst-case complexity, gives no informations about the relative size of this family
 with respect to the size of the class of all invertible finite  $ca$; 
In other words, it was  possible that such  
a particular behaviour was very ``unlikely''   and thus  difficult to generate.
 On the contrary, the dicrete-probabilistic nature of our result shows that, when the closed set of legal
configurations (on which the ca will run on) is also specified, then  this family of invertible $ca$   has an ``important''
 relative size
 and its effective contruction\footnote{From
 a practical point of view, the formal difference between the definition of REV 
and the  generalization, considered in this paper, 
   has no  consequences:  indeed, 
    the  considered closed subset of   legal configurations (i.e. $\Sigma (P,Q_a,x)$) is 
 polynomial-time decidable, hence we can   ``efficiently'' force  the $ca$ to ``run'' only on 
legal starting configurations.}
 could define an interesting class of {\em one-way functions} having the well-known 
practical applications in pseudo-random generators and in cryptology.
 
\medskip
\noindent
{\bf Acknowledgments.}
We would like to thank Prof. P. Mentrasti and 
Prof. T. Toffoli for helpful and very crucial  comments and advices during this work.


\begin{thebibliography}{99}

 \bibitem{[BGLVZ93]}  Bennett C.H.,  Gacs P.,  Li M.,  Vitanyi P. and Zurek  
 W. (1993),
 Thermodynamics of Computation and Information Distance,  Proc. of 25th. 
ACM STOC, p. 21.
 
   
		
 \bibitem{[BP93]} Bilardi G., Preparata F. (1992), Horizons of 
Parallel Computation, Proc. of   Symp. of $25^{th}$ Anniversary of 
INRIA, Springer-Verlag  LNCS, 653, p. 155.

 \bibitem{[C 94]} Clementi A. (1994), On the complexity of Cellular Automata,
PhD thesis, University of Rome ``La Sapienza''.
  
\bibitem{[APP 94]}  Clementi A., Mentrasti P. and  Pierini P. (1994), Some results on invertible cellular automata,
  Submitted to IEEE PhysComp `94.


 
\bibitem{[CP 92]}  Clementi A. and  Pierini P. (1992), Computational 
Complexity of 
the Finite Cellular Automata Reversibility Problem,
  Proc. of the  $IV$ Italian Conference on Theoretical Computer 
Science, World Scientific, p. 165.

\bibitem{[MR 93]} Durand B. (1993), Global invertibility on finite cellular automata, to appear in
 Theoretical Computer Science.

\bibitem{[DF 89]} Dyer M. and Frieze a. (1989), The solution 
of some random $NP$-complete
 problems in polynomial expected time, J. of Algorithms, 10, p. 451.
 
 
\bibitem{[GaJo79]} Garey M. R.,   Johnson D. S. (1979),
 {\em Computers and 
intractability. A guide to the theory of NP-completeness} 
Freeman and Company.
 
 \bibitem{[Gr 87]} Green F. (1987), NP-complete problems in cellular automata,
 Complex Systems, 1, p. 453.

  \bibitem{[Gu91]} Gurevich Y. (1991),   Average-Case Completeness, J. of
Computer and System   Sciences, 42, p. 346.



\bibitem{[JaSo 90]} Jacopini G. and  Sontacchi G. (1990), Reversible Parallel
Computation: an evolving space model, Theoretical Computer Science, 73, p. 
1. 
 
\bibitem{[Ja 90]} Kari J. (1990), Reversibility of 2D cellular 
automata is undecidable,
		Physica D, 666, p.  379.
  
\bibitem{[Jao 94]} Kari J. (1994), Reversibility and surjectivity problems of cellular automata,
 J. of Computer and
System Sciences, 48, p. 149.

\bibitem{[K 77]} Kucera L. (1994),  Expected behaviour of graph coloring algorithms, 
Foundations of Computation Theory '77, Springer-Verlag LNCS, 56, p. 447.
 
\bibitem{[Le86]} Levin  L. (1986), Average-Case Complete Problems, 
SIAM J. of
 Computing, 15, p. 285.


 
 
%\bibitem{[PaLe]} Lewis H.R., Papadimitriou C.H. (1981), {\em Elements of
%the theory of computation}, Prenctice Hall.
  
 
 \bibitem{[Su89]} Sutner K. (1989),  Computational 
 	complexity of finite cellular automata,
	Tech. Rep.,  Stevens Institute of Technology, Hoboken, NJ 07030 
	USA. (It will appear in Complex Systems).


 
%\bibitem{[Su 91]} Sutner K. (1991), De Bruijn Graphs and Linear Cellular
%Automata, Complex Systems, 5, p. 19.
 
 
\bibitem {[ToMa90]}  Toffoli T.  and   Margolus N. (1990), Invertible
 cellular automata: a 
review,
 Physica D, 666, p. 1.
 
  

 \bibitem{[Wo 85]} Wolfram  S. (1985),
		  Twenty problems in the theory of cellular automata,
         Physica Scrypta, T9, p. 170.


  \bibitem{[WW86]} Wolfram S. (1990), Approaches to complexity
 engineering, Physica D, 22, p. 246.


 

\end{thebibliography}



 
\end{document}

____________________________
\medskip

A Non Deterministic Turing Machine (NTM) {\em survives} for $n$ steps
on input $w$ if there exists a computation of $M$ on $w$ with at least $n$ 
steps. We 
shall consider NTM whose input alphabet is the binary one.

\medskip
\noindent
{\bf Randomized Survival Problem $RS(M,w,n)$}


\noindent
 \underline{Instance:} A NTM $M$, the  unary notation  of a positive integer 
$n$ and  a 
binary 
string $w$ such that $|w|<n$.

\noindent
 \underline{Question:} Does $M$ for $n$ steps on input $w$ survive?

\noindent
 \underline{Probability:} Any positive probability function on the set of 
all NTM $M$ (that is,
the particular choice of the distribution on the NTM set 
is not crucial for the completeness
of the problem); choose $n$ with the ``standard''
 probability (i.e. proportional to $1/n^2$); choose uniformly
$k<n$ (i.e. with probability $1/n$); choose uniformly a 
binary string $w$  of lenght $k$ (i.e. with probability  $1/2^k$).

\medskip

-------------------------------------


%----- pezzi staccati ---------------%

\begin{definition}  \label{PD}
Given a $ah$- $ ca$ $\langle A=(Q,N,f),x \rangle $ on a $n\times n$ torus, 
we define its {\em partially disabled}
version $A_{PD} =(Q \times \{ Red, Green \},N,f_{PD})$ where:  

\begin{itemize}

\item For any cell $(i,j) \neq ( \lceil n/2 \rceil,\lceil n/2 \rceil ) $ we have:

\[ f_{PD}(p_1 ;p_2 ,\ldots,p_k) = \left\{ \begin{array}{ll}
Identity \: function  & if \: p_1 = [*,Red],\:  or  \: 
 p_1 = [q_1=(\beta,q'),*]\: for\: a\: fixed\: element\\

 & \beta \in Q^{\beta} \: (where\: Q^{\beta} \:is\:  Q \: or \: a \:component \: of \: 
 it) - Disabled \: cell\\ & \\
(f(q_1 ;q_2 , \ldots,q_k ), Green) & otherwise 
\end{array} \right.\]

Informally, if the colour component of a cell is green and the $Q^{\beta}$ component
is not equal to $\beta$ (disabled state) then   $f_{PD}$ simulates
$f$, otherwise $f_{PD}$ keeps the state unchanged.


\item  For the ({\em central}) cell $(\lceil n/2 \rceil,\lceil n/2 \rceil)$, $f_{PD}$ 
has a symmetric behaviour respect to the  $Q^{\beta}$ component:


\[ f_{PD}(p_1 ;p_2 ,\ldots,p_k) = \left\{ \begin{array}{ll}
Identity \: function  & if \: p_1 = (*,Red),\:  or  \:  p_1 = [q_1=(h',q'),*]  \\
 & with\: \beta' \neq \beta  - Disabled \: cell\\ & \\

(f(q_1 ;q_2 , \ldots,q_k ), Green) & otherwise \end{array} \right.\]

\end{itemize}
\end{definition}

--------------

\subsection{ An instance of the tiling problem}

Let us adapt the tile edge colours definition given in section \ref{defi}.
We shall consider a tiling technique proposed in [Ro76] and modified in
[Ka90].  The main difficulty in our case lies	 in the fact  that such a  general 
technique has been defined and used only for infinite supports. Keeping global 
properties
in the passage from aninfinite support to a finite one is a central 
problem in the theory of cellular automata (see [To90], [Wo86], [Su88]). The
 periodical conditions arising when cellular automata are defined on finite toroidal
structures do not permit to transform such a technique in a simple way.


Each tiles colour is replaced by two components:

\begin{description}
\item[$\alpha)$] one labelled arrow 
\item[$\beta)$] one or more passages, each of them is a pair
 $(inward \: direction,
 outward \: direction)$ of elements of the set \\
$\{S,SW,W,NW,N,NE,E,SE\}$
\end{description}

Regard to arrow components we can have tiles as shown in the following figure 

\input figura1.tex

\noindent
Fig. 1.  $xy\in\{NE,NW,SE,SW\}$ 
{\em (defined up to 90¡ rotation)}
\vspace {7mm}


Single and double arms have labels forced as in the following figure:

\input figura2.tex

\noindent
Fig. 2.  $x\in \{E,W\}, y\in \{N,S\}$ 
{\em (identically for double arms)}
\vspace {7mm}



Mixed arms have labels forced as:

\input figura3.tex

\noindent
Fig. 3
%\noindent

%\vspace {5mm}

About passages we have:
\begin{itemize}
\item Double crosses must have the passages $\{(NW,NE),(NE,SE),(SE,SW),(SW,NW)\}$;

\item Single crosses must have one of the following six passages sets:\\
$\{(XY,XY)\}$ such   that $ XY\in \{NE,NW,SE,SW\} $ or
 $ \{(NW,SE),(SE,NW)\}$ or $\{(NE,SW), (SW,NE) \}$.

\item no passage for any type of arms.
\end{itemize}

%%------------------------------------------------------
In order to force the correct position in the final  tiling ,  we need to add eight 
collections of arrows, denoted as 
{\em bold}.

\input figura6.tex

\noindent
Fig. 4.  $NW^{NE}$ {\em bold arrows collection: $a)$ crosses with label $NW$ , 
$b)$
crosses with labels $SW$ or NE, $c)$ upwards arms with label $NW$, $d)$ and
$e)$ horizontal arms.}
%\noindent

\medskip
If the arrow coming from the lower edge of an horizontal arm has label  
NW then the tile must have one of the three bold arrows patterns of figure;
this is the only type of tiles that necessarily must contain a bold arrow 
of this collection. In symmetric way (see for example 
figure 6) the other seven collections can be
determined: $NW^{SW}$, $NE^{NW}$, $NE^{SE}$, $SE^{NE}$, $SE^{SW}$, 
$SW^{NW}$ and $SW^{SE}$.

The global set of tiles above defined is the same used in [Ka90] and will be denoted as 
${\tau}^{PF}$.

%%------------------------------------------------
\begin{definition} \label{coti}
According to the new tile definition, a tiling  is correct iff:
\begin{description}
\item[{\em i)}] each arrow (bold or not) head meets an equal arrow tail with the same
 label.
\item[{\em ii)}] for each passage the neighboring tile in the outward 
direction has the passage with the opposite inward direction.

\end{description}
\end{definition}

\vspace{3cm}


\hspace{2cm} $a$  \hspace{7cm} $b$
\nopagebreak
\input figura4-5.tex 
\nopagebreak
\noindent
Fig. 5.  {\em $a)$  constructing the $(2^{n+1}-1)$-XY-square. $b)$ 
The 7-XY-square
 with labels on the crosses. Only the principal arrow of the
arms are drawn.}



\input figura6a.tex
\nopagebreak

\noindent
Fig. 6. {\em The  7-NW-square with the $NW^{NE}$ and $NW^{SW}$ bold arrows.}
\vspace {5mm}

On a ${\tau}^{PF}$ tiling, we define a path be a sequence of consecutive passages $p_1,
/ldots,p_l$ associated with neighboring cells, such that for $i=1,\ldots,l-1$, the outward
direction of $p_i$ is equal to the inward direction of $p_{i+1}$.
For each
natural number $n$ we can recursively define a correct tiling on a 
$(2^n -1)$-square (sse fig. 5.1) also considering bold arrows 
 (see fig. 6). Bold arrows will be  
strongly used to prove 
lemma \ref{38}.

\subsection{ An $ah$- $ ca$ having the $XOR$ property }

In order to define an $ah$- $ ca$ having the $XOR$ property we now introduce the following
tile sets that consider the size an the toroidal structure of the system.
%\pagebreak

\noindent
{\bf -} \underline {Set of {\em Edge} tiles $\tau^{ED}$}:

\input figura7a.tex

\input figura7b.tex

\noindent
Fig. 7.  

\medskip
More precisely:


\begin{description}
\item[$a)$] {\em Corner cross} has no passages and no bold arrows.
\item[$b),c)$] {\em Single and double ED-arms pointing left or upwards }
 $x\in \{E,W\}, y\in \{N,S\}$ have no passages  and same bold arrows of
 horizontal (or vertical) arms defined above.
\item[$d),e)$] {\em Mixed ED-arms pointing left (upwards)}, the two single meeting
 arrows can only have label  $CE$. They have 
no passages and the same bold arrows of horizontal (vertical) arms 
defined
above. Such tiles can have bold arrows of each collection $NW^{NE}$, 
$NE^{NW}$, $SW^{SE}$, $SE^{SW}$ ( $NW^{SW}$, $NE^{SE}$, $SW^{NW}$, 
$SE^{NE}$ ).
\end{description}

\noindent
{\bf -} \underline{Set of {\em Center} tiles  $\tau^{CE}$}:

\input figura8.tex

Fig. 8.

\medskip
More precisely:


\begin{description}
\item[$f)$] {\em Single, double and mixed CE-arms (up to 90¡ rotation)},
head and tail of principal arrows have label 
 $CE$. They have the 
same behaviour of $\tau^{PF}$ arms.
\item[$g)$] {\em Double CE-cross} has passage like the other double crosses
and no bold arrows.
\end{description}

\begin{lemma} \label{new} Let 
 $XY^{AB}$ be an element of the set $\{NW^{NE},$ $ NW^{SW},$ $ NE^{NW},$ $ NE^{SE},$ 
$ SE^{NE},$
$ SE^{SW},$ 
$ SW^{NW},$ $ SW^{SE}\}$.  
Let {\em H} be the $XY$-half of
 the $(2^k -1)-XY$-square, $k=1\ldots n-1$, on the $2^n \times 2^n$ torus.
Suppose that the tiling is correct both on {\em H} and on all the neighboring
tiles as well. Then the tile in the  $AB$ corner of the neighborhood
of {\em H} cannot be a cross.
\end{lemma}

\proof Let us give a sketch of proof. Without loss of generality consider the tile $T$
in the $NE$ corner of a $NW$-square in figure 6. Suppose $T$ is a cross, so it cannot have 
$NW^{NE}$ bold arrows like in figure 6. Thus a tiling error occurs contradicting
the hypothesis. Note that neither bold arrows nor restrictions are forced to the 
corners of the  $CE$-square.
\eproof

	It is not hard to verify that:

\begin{lemma}\label{37} Let $H_1$ and $H_2$ be two halves (respect to 
diagonal)
of a correct tiling of $(2^n -1)$-squares on the plane 
and suppose that there is a single cross that belongs  both  to $H_1$ and 
$H_2$. Then the central crosses of $H_1$ and $H_2$ coincide i.e. if the
two halves overlap then they must belongs to the same square.
\end{lemma}


\begin{definition} \label{AH1}

Let $n$ be a natural number. We define the following  $2^n \times 2^n$ 
$ah$- $ ca$ $AH=\langle A=(Q,N^m,f),x \rangle $:


\begin{itemize}
\item Each $q\in Q$ is composed of two components:
\begin{itemize}
\item[{\em i}] A tile $t\in \tau^{T}$ where $\tau^{T}=\tau^{PF}\bigcup\tau^{ED}\bigcup
\tau^{CE}$
(we assume that 
a tiling error occurs in the neighborhood of a cell if 
there is tiling error respect to this component that we 
shall simply denote
as tile.).

\item[{\em ii}] One bit (0 or 1) for each passage of $t$.
\end{itemize}


\item The function $f$ does not change the tile component. Let us suppose there 
are no 
tiling errors in the neighborhood of a cell $i$, then the function
$f$ operates the $XOR$ between the  bit of each  passage $p$ of $i$ and the
bit of the next corresponding passage on the path. On the contrary, if there is a tiling 
error, bits remain unchanged.
\item The choice of the string $x$ does not affect the $XOR$
property.

\end{itemize}
\end{definition}

\begin{definition}  \label{Ner}

Given an arbitrary configuration $c$ we say that a {\em neighborhood error} 
occurs in a cell if at least one of the following situations happens:

\begin{description}
\item[$a)$] Concerning the partially disabled version of $AH$ where 
the element $\beta$ (see def. \ref{PD}) is set to be the double cross labeled
with $CE$, the cell is disabled (intuitively, there is a $CE$ double cross in a 
"wrong" position).

\item[$b)$] Concerning the tile components, there is  a  tiling error in the
cell  neighborhood.

\end{description}
\end{definition}


\begin{lemma}     \label{38} 
Let $n$ be a natural number and consider a configuration
$c$ of the $2^n \times 2^n$ $ah$- $ ca$ defined in \ref{AH1}. Let $P$ be a passage
attached to a single cross $\alpha$ in a $c$  cell. For any fixed   
$m \leq n$,  consider the cell  set  
including 
$\alpha$ as well as the $2^{2m}$ cells (eventually considered more than 
one time)  preceding $P$ and the $2^{2m}$ cells  succeeding  $P$ on the
path (eventually cyclic) through $P$ and suppose that there are no 
neighborhood
errors (see def. \ref{Ner}).

Then,   $P$ belongs to a path through a half of a $(2^m -1)$-square.

\end{lemma}

\proof
 We prove the lemma by induction on $m$. If $m=1$ the single cross
$\alpha$ is the required 1-square. Suppose the lemma is true for $m<n$, then
we shall prove the lemma for $m+1$. Consider the $2^{2(m+1)}$ passages
preceding and succeeding $P$; for inductive hypothesis, $P$ belongs to a
path through a half of a $(2^m -1)$-square $S$.  
The  central cross
of the $(2^m -1)$-square cannot be labeled with $CE$, since  in this case, either
$m = n$ or the absence of neighborhood error would be contraddicted (see def. 
\ref{Ner}-$a)$ . 

Since the
$(2^m -1)$-square central cross cannot be labeled with $CE$ we can 
 suppose, without loss of generality, that it is labelled with SW. Four cases
may arise. In the following we shall refer to figure 10.


\input figura9a.tex

Fig. 10.


\vspace {5mm}

\begin{description}
\item[$1)$] If the half of $S$ is the $NE$ one we have a contraddiction with the 
inductive hypothesis; observe that tiles $A$ and $B$ may not
be a cross.The tile $C$ in figure may not be 
a double cross, otherwise $D$ would have the 
passage $(SW,NE)$ and  
the path should leave the 
square; the inductive hypothesis would be false. So $C$ must be an arm or
a corner-cross, it follows that either the tile on the left of $C$ or
the tile below $C$ must be an arm oriented to $C$, hence $A$ or $B$ (or both)
 must be an arm pointing towards $C$ whose meeting arrows, coming from the 
square  $S$, are labeled with SW. 
This is an absurd since such tiles do not exist.

\item[$2)$] If the half of  $S$  is the $SW$ one, by lemma  \ref{new}, the tiles $E$
and $F$ are not crosses, so $G$ must have passage $(SE,SE)$.
The head of this passage, by inductive hypothesis, must be on a path
through a half of some $(2^m- 1)$-square; such a half and the considered
 $S$ half share tile $G$ so, from lemma  \ref{37}, they have the same central
cross. We conclude that the passage on $G$ belongs to a path $p_1$ visiting
the $NW$  half of $S$. In anologue way we can show that $H$ belongs to a path 
$p_2$ through the $SE$ half of $S$. Since $P$ belongs to $p_1$ or  $p_2$ the
following case can always be applied.

\item[$3)$] The cases $NW$ and $SE$ halves are symmetric, thus it is not 
a restriction to consider only the $NW$ one. Tile $C$ must be a double
cross otherwise $D$ would have  the passage $(SW,SW)$ and there would be a 
path through the $NE$ half of $S$.
Such a situation has been considered in  case $1)$ and has been shown
impossible. The considered path visits succesively tiles $D$,$C$ and $I$;
applying the inductive hypothesis on $I$ its passage must be on a
path through a half of some $(2^m - 1)$-square, such a half will be
denoted as $H_1$. By lemma \ref{37} if $D$ belongs to $H_1$ this 
half and the $NW$ half of $S$ would have a common central cross, but this is not
 possible because $I$ is too far from the $S$ central cross, thus, such two halves
must be distinct.
Therefore, the passage on $I$ must be the first one on the path through
$H_1$ (see figure). Since tile $A$ is forced to be a mixed arm, 
the $H_1$ central cross must be labeled with $NW$. The path continues 
from tile $I$ through $H_1$ to the tile $N$. Both tiles $L$ and $M$ cannot
be double crosses;  suppose on the contrary that $L$ and $M$ are
 double crosses. The tiles between $L$ and $M$ are arms; since the labels
of the right meeting arrows of such a tiles must be $SW$ or $NW$ , we can have
only one mixed arm in the tile $E$ and this is an absurd. Suppose, without
loss of generality, that tile $L$ is not a cross. The passage of $N$ is of 
the type $(SE,SE)$, thus it belongs to the path through the $NW$  half
of the $NW$-square. By lemma \ref{new} tile $Q$ may not be a cross;
again with the same line of reasoning used above, the path from $O$ continues
through the $NE$ half of the $NW$-square back to $C$. As showed for the tile
$I$ it is easy to verify that the path goes, via $R$, through the $NW$  half
of the $(2^m - 1)$-NE-square placed on the right of the $NW$  one.
The global path described above goes through the $NE$ half of the
$(2^{m+1} -1)$-square. Note that such a path include less than
$2^{2(m+1)}$ passages, thus the lemma is proved.
\end{description}

\eproof


\begin{theorem} \label{310}
The $ah$- $ ca$ $AH$ defined in \ref{AH1} has the $XOR$ property.
\end{theorem}

\proof  
The proof is structured in three steps:

\begin{description}
\item[$1)$] For any $AH$ configuration, we prove that given an arbitrary
path either\\
$\alpha)$ it visits all the cells having a cross as tile component\\
or\\
$\beta)$ some neighborhood error occur.

\item[$2)$] Since in a correct tiling every $2 \times 2$ block of cells contains
a cross, we can consider each final cell to be composed of one of 
these $2 \times 2$ blocks of elementary cells. In this way, the property 
$\alpha$ in step $1)$ is equivalent to require that the path visits all the final  cells
instead of all the elementary cross cells.

\item[$3)$] Using steps $1)$ and $2)$ we shall prove the $XOR$ property of
$AH$.

\end{description}

Let us prove in detail steps $1)$ and $3)$.

\begin{description}
\item[$1)$] Let us consider a path with no neighborhood error.
For  lemma \ref{38} such a path 
covers every cross of some  halves  of a $(2^n -1)$-square $S$,  suppose
without loss of generality that the half is the $NW$  one.

\input FIGURA10

\noindent
Fig. 11.

\vspace {5mm}

Cell  $C$ in figure 11 may not be a double cross,  otherwise $G$ would
 have the 
passage $(SE,NW)$ and   the path would leave the 
square through it. The distance between cell $C$ and   cell $B$ is $2^n$;
since we are on a $2^n \times 2^n$ torus support,   cells $C$ and $B$ must
coincide. Similarly for   cells $C$ and $D$. It follows that both $B$ and 
$D$ are not double crosses. The passages attached to the single crosses 
$E$ and
$F$ are respectively of the type $(NE,NE)$ and $(SW,SW)$. The head of the 
$F$ passage is on the path through a half of some $(2^n -1)$-square.
 Such half
and the $NW$-half share $F$, so for lemma \ref{37}, $F$ is on a path through
the NE-half. Applying the method described above to the   cell $H$ and, then,
to the   cell $E$,
we find a closed path through the entire $S$. Under these intial 
hypothesis, $A$ must be labeled with $CE$ and the tiles surrounding $S$
must be ED-tiles.

\item[$3)$] Let us consider  the two $AH$ configurations $c_1$ and $c_2$ 
having respectively all the bits (see def. \ref{AH1} - {\em i})
set to 0 in $c_1$ and set to 1 in $c_2$ and with
no neighborhood error.

 According to the local rule, we have 
$F(c_2)=c_1=F(c_1)$, then  $AH$ is not injective.

Suppose that $c_1$ and $c_2$ are different configurations of the partially
disabled version of $AH$, and $F_{PD}(c_1)=F_{PD}(c_2)$. The tiles on 
$c_1$ and $c_2$ must coincide. Consider a passage whose bit is different 
in $c_1$ and $c_2$. The correspoding state must be coloured green, there
is not neighborhood error on the cell  and the bit of the next passage on the path
must be different in $c_1$ and $c_2$. Iterating such process, every cell on
the path must be coloured green and not disabled.  By step $2)$ the path covers
every $AH$ cell, then the $XOR$ property is proved. 
\end{description}
\eproof 



\subsection{$RNP$-completeness of RNIP} \label{toro}


Let us show how  to transform a set of tiles $\tau$ to another 
set  $\tau^*$ such that $\tau$ has a correct tiling for the $(2^n -1)\times (2^n -1)$
lattice iff $\tau^*$ has a correct one for the $2^n \times 2^n $ torus. Even
for this result we shall use the set of tiles used in the last section.
 Let $C$ be the  colour set associated
to $\tau$,  then, the  set $\tau^*$ is defined as follows: \\
$\tau^*=[\tau \times (\tau^{PF} \cup \tau^{CE} )] \cup (C^4 \times 
\tau^{ED})$ 

Informally, for each tile $\alpha$ of $\tau$ let us "paint" all the tiles of
 $\tau^{PF}$ and $\tau^{CE}$ according to  $\alpha$ and
 "paint"
$\tau^{ED}$-tiles with all possible colours. If $\tau$ admits
a correct tiling $g$ on the $(2^n -1)\times (2^n -1)$ square,
 let us consider the correct
tiling determined  by $\tau^{PF}$ and $\tau^{CE}$ tiles
 and attach to such tiles the colour components defined by
$g$; we complete the $2^n \times 2^n $ torus with tiles in $(C^4 \times 
\tau^{ED})$ since these tiles have no restrictions about colour components.
Conversely, suppose that  $ \tau^*$ admits a correct
 tiling on the torus. 
We know that tiles with ED labels can only be located in the border of size $2^n$ 
(up to traslation); thus,  we can cut such tiles and consider only the colour 
components of the remaining tiles: we have obtained a correct tiling
for a $(2^n -1)\times (2^n -1)$ square. Observe that the cardinality of $\tau^*$
does not depend  on $n$.




\bibitem{[Ri72]} D. Richardson, {\em Tesselations with local transformations,
 J. Comput. System Sci.} {\underline 6} (1972) 373.

\bibitem{[Ro71]} R.M. Robinson, {\em Undecidability and non periodicity for 
tilings of the plane, Inventiones Mathematicae} {\underline {12}} (1971) 177.

%\bibitem{[Sm71]}  A. R. Smith III, {\em Cellular automata complexity 
%trade-offs, 
%Info. Control} {\underline {18}} (1971) 466. 


