%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}_{x0\}$ 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 $i1$, an integer $j$ such that $01 \}$, 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