% The Chicago Journal of Theoretical Computer Science, Volume 1999, Article 2
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1999 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{\setof}[2]{\left\{\,#1:#2\,\right\}}
%
\tolerance=9000

\newcommand{\range}{{\rm range}}
\newcommand{\union}{{\,\cup}\,}
\newcommand{\interset}{{\,\cap}\,}
\newcommand{\naturals}{\mbox{\sf I \hspace{-.8em} N}}
\newcommand{\integers}{\mbox{\sf Z \hspace{-1.1em} Z}}


\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 1999, Article 2\\
      \textit{24 February 1999}
    \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 1999 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to ensure 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{1999}
%
\articleid{2}
%
\selfcitation{
     @article{cj99-02,
       author={Jie Wang},
       title={Randomized Reductions and Isomorphisms},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1999},
       number={2},
       publisher={MIT Press},
       month={February},
       year={1999}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Randomized Reductions and Isomorphisms}
\shorttitle{Randomized Reductions}
\collectiontitle{Special Issue on Computational Complexity}
\editorname{Eric Allender}
%
\editorcomment{\samepage%
This article is included in the \emph{Special Issue on
Computational Complexity} containing articles 
based on selected presentations made at the Dagstuhl-Seminar
\emph{Structure and Complexity}, held September 30---October 4, 
1996, at Schlo\ss\ Dagstuhl, Germany\@. This special issue was 
edited by Eric Allender\@.
}
%
\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{Jie Wang}
   \collname{}{Wang, Jie}
   \begin{institutioninfo}
       \instname{The University of North Carolina at Greensboro}
       \department{Department of Mathematical Sciences}
       \address{}{Greensboro}{NC}{27402}{USA}
   \end{institutioninfo}
   \email{wang@uncg.edu}
\end{authorinfo}
%
\shortauthors{Wang}
%
\support{
Supported in part by NSF under grant
CCR-9424164 and by a research grant from the University of North
Carolina at Greensboro.
}
%
\begin{editinfo}
  \submitted{05}{06}{1997}\reported{01}{02}{l998}
  \submitted{02}{02}{1998}\reported{09}{02}{l998}
  \submitted{04}{09}{1998}\published{24}{02}{1999}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}


\begin{abstract} 
Randomizing reductions have provided new techniques for tackling
average-case complexity problems\@. For example, although some 
NP-complete problems with uniform distributions on instances 
cannot be complete under deterministic one-one reductions \cite{cj99-02-21}, they
are complete under randomized reductions \cite{cj99-02-17}\@. 
We study randomized 
reductions in this paper on reductions that are
one-one and honest mappings over certain input domains\@.
These are reasonable assumptions 
since all the randomized 
reductions in the literature that are
used in proving average-case completeness results
possess this property\@. We consider whether randomized
reductions can be inverted efficiently\@. This gives rise 
to the issue of randomized isomorphisms\@.
By generalizing the notion of isomorphisms under deterministic
reductions, we define what it means for two distributional
problems to be isomorphic under randomized reductions\@. We 
then show a randomized version of the
Cantor-Bernstein-Myhill theorem, which provides a sufficient
condition for two distributional problems to be 
isomorphic under randomized reductions\@. Based on that condition 
we show that all the known average-case NP-complete problems (including
those that are complete under deterministic reductions)
are indeed isomorphic to each other under randomized reductions\@.
\end{abstract}

\asection{1}{Introduction}
%
\apar{1-1}
Average-case complexity has attracted increasing attention recently\@.
A major objective of this study is to identify
(standard, worst-case) NP-complete problems that are difficult,
on average, from those that are easy, on average\@. Various notions of
reductions for distributional problems are
useful tools for studying average-case complexity\@.
A distributional problem is a pair consisting of
a problem \(A\) and a probability distribution \(\mu\) on
instances of \(A\)\@. If \(A\) is an NP problem, then 
we call \((A,\mu)\) a distributional NP problem\@.
Deterministic reductions are
simpler and easier to use; they have been used to prove
that some NP-complete problems under plausible distributions
are average-case complete\@.
However, deterministic reductions have certain limitations\@.
For example, under the assumption that EXP \(\not=\) NEXP,
distributional NP problems with flat distributions cannot be
complete under deterministic reductions \cite{cj99-02-09};
and (without any assumption) distributional NP problems with
flat distributions cannot be complete under deterministic one-one
reductions \cite{cj99-02-21}\@. Randomized reductions were introduced
to overcome these limitations \cite{cj99-02-17}\@.
Some NP problems with flat distributions
have been shown to be complete under randomized reductions 
\cite{cj99-02-17,cj99-02-09,cj99-02-07}\@.
Randomized reductions have also been used to obtain several other
interesting results\@. For example, using randomized reductions, 
Impagliazzo and Levin \cite{cj99-02-11} showed that
any NP search problem under any polynomial-time 
samplable distribution is reducible
to some NP search problem under a uniform distribution\@.
This result is also true for NP decision problems under
randomized truth-table reductions \cite{cj99-02-04,cj99-02-20}\@.
Also, using randomized reductions, Belanger
and Wang \cite{cj99-02-03} showed that no NP problems over ranking
of distributions are harder than over uniform distributions\@.
%
\apar{1-2}
Gurevich \cite{cj99-02-09} and 
Blass and Gurevich \cite{cj99-02-06,cj99-02-07} have conducted intensive studies
on randomized reductions\@. Through their work, we have gained deeper
understandings on randomized reductions\@. 
We carry on this study a step further by considering reductions
that are one-one and honest mappings over certain input domains\@.
(A mapping \(f\) is honest
if for any input \(x\), the length of its image \(f(x)\) cannot be too short;
namely, 
there is a polynomial \(p\) such that
for any input \(x\), \(p(|f(x)|) \ge |x|\)\@.)
These are reasonable assumptions since all the randomized 
reductions in the literature that are
used in proving average-case completeness results
possess this property\@. Moreover, we consider whether these 
reductions can be ``inverted" efficiently\@. 
This gives rise naturally 
to the issue of randomized isomorphisms of average-case \allowbreak NP-complete
problems\@. 
%
\apar{1-3}
Berman and Hartmanis \cite{cj99-02-05} were the first to study
isomorphisms of complete sets for resource-bounded
worst-case complexity classes\@. They
defined a notion
of isomorphism under deterministic polynomial-time reductions\@.
They showed that all the known NP-complete sets are 
polynomially isomorphic, and they conjectured that it should also be true
for \emph{all} NP-complete sets\@. 
This conjecture implies that P is different from NP\@.
Although this conjecture has not been
solved, it has stimulated 
a host of papers in structural complexity theory\@.
Wang and Belanger \cite{cj99-02-21} observed that some standard 
NP-complete problems, while isomorphic on the worst case,
are not isomorphic on the average case under commonly used distributions\@.
On the other hand, all the average-case NP-complete problems 
may still be isomorphic\@.
To extend the isomorphism theory of Berman and Hartmanis from worst case
to average case, Wang and Belanger \cite{cj99-02-21} defined a notion 
of isomorphisms for distributional 
problems under deterministic reductions ---
a natural generalization of Berman and Hartmanis' notion of
isomorphisms\@. They showed that 
all the known average-case NP-complete problems that are complete
under deterministic reductions are indeed isomorphic\@.
%
\apar{1-4}
We consider whether the notion of isomorphisms
can be further extended to include randomized reductions, and
we devote this paper to answering this question\@. We
provide an affirmative answer:
By generalizing the notion of isomorphisms under
deterministic reductions,
we define in a natural way what it means for two distributional
problems to be isomorphic under randomized reductions\@.
We then show a randomized version of the
Cantor-Bernstein-Myhill theorem, which provides a sufficient
condition for two distributional problems to be 
isomorphic under randomized reductions\@. Based on that condition 
we show that all the known average-case NP-complete problems (including
those that are complete under deterministic reductions)
are indeed isomorphic to each other under randomized reductions\@.
%

\asection{2}{Average Time and Instance Distributions} \label{s:pre}
%
\apar{2-1}
We provide in this section basic definitions and results 
of average-case complexity\@. For a recent survey of average-case complexity,
its motivations, traps and escapes,
the reader is referred to \cite{cj99-02-09,cj99-02-20}\@.
%
\apar{2-2}
Let \(\Sigma = \{0,1\}\)\@. We assume that all languages are subsets of
\(\Sigma^*\)\@. Let \(\mu\) denote a probability distribution (distribution,
in short) over \(\Sigma^*\); i.e., \(\mu\) is a real-valued function from
\(\Sigma^*\) to [0,1] such that \(\sum_x \mu(x) = 1\)\@.
The probability distributions we consider are on instances of
computational problems\@. If a binary string does not encode an instance
of the underlying problem, then that string has zero probability\@.
The \emph{distribution function} of \(\mu\), denoted by \(\mu^*\), is
defined by \(\mu^*(x) = \sum_{y\leq x}\mu(y)\), where \(\leq\) is
the standard lexicographical order on \(\Sigma^*\)\@.
For a function \(f\), we use \(f^\varepsilon(x)\) 
to denote \((f(x))^\varepsilon\) for 
\(\varepsilon > 0\) and we use \(f^{-1}\) to denote the inverse of \(f\)\@.
We use \(\naturals\) to denote the natural numbers\@.
We will consider decision problems in this paper;
we will omit the word ``decision" when there is no confusion\@.
%
\apar{2-3}
Levin \cite{cj99-02-14} suggested to use \emph{multi-median} time to measure
average computation time, and he gave the following definition\@.
%
\begin{alabsubtext}{Definition}{1}{\cite{cj99-02-14}}
%\begin{definition} 
A function \(f: \Sigma^+ \rightarrow \naturals\) is \emph{polynomial on
\(\mu\)-average\/} if there is an \(\varepsilon > 0\) such that
\(\sum_x f^\varepsilon(x)|x|^{-1} \mu(x) < \infty\)\@.
\end{alabsubtext}
%\end{definition}
%
\apar{2-4}
This notion of average time is robust and machine independent\@.
%
\apar{2-5}
Let AP denote the class of all distributional problems
\((A,\mu)\) such that \(A\) can 
be solved by a deterministic algorithm whose running time is 
polynomial on \(\mu\)-average\@. AP is an average-case analogue of P\@.
%
\apar{2-6}
In what follows, we will use ``p-time'' to denote ``polynomial-time,''
and ``ap-time'' to denote ``average-polynomial-time\@.''
%
\apar{2-7}
Let \(\mu\) and \(\nu\) be two distributions; then
\(\mu\) is \emph{dominated by} \(\nu\),
denoted by \(\mu \preceq^p \nu\), 
if there is a polynomial \(p\)
such that for all \(x\), \(\mu(x) \le p(|x|) \nu(x)\)\@.
%
\apar{2-8}
A real-valued function
\(r:\Sigma^* \rightarrow [0,1]\) is p-time computable if
there exists a deterministic algorithm \({\cal A}\) such that for every
string \(x\) and every positive integer \(k\), \({\cal A}\) outputs a finite
binary fraction \(y\) such that \(|r(x)-y| \le 2^{-k}\) and
the running time of \({\cal A}\) is polynomially bounded in \(|x|\) and
\(k\) \cite{cj99-02-13}\@. Clearly, if \(\mu^*\) is p-time computable, then so is
\(\mu\); but Blass showed that the 
converse is not true unless P = NP (see \cite{cj99-02-09})\@. 
With this fact in mind, we assume throughout that
when we say that \(\mu\) is p-time computable, 
both \(\mu\) and \(\mu^*\) are p-time computable\@.
%
\apar{2-9}
Levin (see \cite{cj99-02-12}) hypothesized that any natural distribution
\(\mu\) is either
p-time computable or is dominated by a distribution that is\@.
Strong evidence that supports this hypothesis is the fact that
all the commonly used discrete distributions do satisfy this hypothesis\@.
It is often natural to consider uniform distributions\@.
We say that a distribution \(\mu\) is \emph{uniform} 
if \(\mu\) is p-time computable
and, for all \(x\), \(\mu(x) = \rho(|x|)2^{-|x|}\),
where \(\sum_n \rho(n) =1\) and there exists a polynomial \(p\) such
that for all but finitely many \(n\), 
\(\rho(n) \geq 1/p(n)\)\@.
Levin~\cite{cj99-02-14} used \(n^{-2}\) for \(\rho(n)\) for notational
convenience (normalized by dividing by 
\(\sum_n n^{-2} = \pi^2/6\)), and
\(|x|^{-2}2^{-|x|}\) is often referred to as
the \emph{default} uniform distribution\@. 
If an instance \(X\) consists of several parameters \((x_1,x_2, \dots, x_k)\), 
then by uniform distribution of \(X\) we mean that each parameter \(x_i\) 
is selected independently and uniformly with respect to the 
default uniform distribution on \(x_i\)\@.
%
\apar{2-10}
Let DistNP denote the class of distributional problems \((A,\mu)\) 
such that \(A \in\) NP and \(\mu\) is either p-time computable or
is dominated by a distribution that is\@. By Levin's hypothesis,
DistNP includes all natural distributional NP problems\@. DistNP
is a distributional analogue of NP\@.
%

\asection{3}{Deterministic and Randomized Reductions}
%
\apar{3-1}
Several NP-complete problems under uniform distributions have been
shown to be in AP (e.g., see \cite{cj99-02-12,cj99-02-10})\@.
To find out whether there are complete problems for DistNP,
Levin \cite{cj99-02-14} defined and used the notion of polynomial-time many--one
reducibility\@. Gurevich \cite{cj99-02-09} conducted a thorough investigation
on this notion\@.
%

\asubsection{3.1}{Deterministic Reductions}
%
\apar{3-1.1}
Let \(f\) be a function from \(\Sigma^*\) to \(\Sigma^*\)\@.
Write \(f(\nu)(y)\) to denote \(\sum_{f(x) = y}\nu(x)\)\@.
Then \(f\) induces a distribution \(f(\nu)\) on \(\Sigma^*\) for the outputs
of \(f\)\@. We say that \(\mu\) is \emph{dominated by
\(\nu\) with respect to \(f\)}, denoted by \(\mu \preceq_f^p \nu\), if there
exists a distribution \(\mu_1\) such that \(\mu\) is dominated by
\(\mu_1\) and, 
for all \(y \in \) range(\(f\)), \(\nu(y) = f(\mu_1)(y)\)\@. 
%
\begin{alabsubtext}{Definition}{2}{\cite{cj99-02-14,cj99-02-09}} \label{d:2} 
Let \((A,\mu_A)\) and 
\((B,\mu_B)\) be two distributional problems\@.
Then \((A,\mu_A)\) is \emph{p-time many--one reducible to} \((B,\mu_B)\),
denoted by \((A,\mu_A) \leq_m^p (B,\mu_B)\),
if there exists a 
p-time computable reduction \(f\)
such that \(A\) is many--one reducible to \(B\) via \(f\) and
\(\mu_A \preceq_f^p \mu_B\)\@.
\end{alabsubtext}
%\end{definition}
%
\apar{3.1-2}
Polynomial-time many--one re\-duc\-tions have the desired properties 
\cite{cj99-02-09}:
If \((A,\mu_A) \leq_m^p\) \((B,\mu_B)\) and \((B,\mu_B) \in {\rm AP}\), 
then \((A,\mu_A) \in {\rm AP}\); 
polynomial-time many--one reductions are transitive\@. 
%
\apar{3.1-3}
The requirements of p-time 
many--one reductions can be weakened in two ways without losing
the two desired properties \cite{cj99-02-14,cj99-02-09}\@.
%
\apar{3.1-4}
First, we may require only that the
reduction be computable in time polynomial
on \(\mu_A\)-average\@. 
%
\apar{3.1-5}
Second, we may use the following
weaker domination condition\@.
Distribution \(\mu\) is \emph{weakly dominated by} \(\mu_1\),
denoted by \(\mu \preceq^{ap} \mu_1\),
if for all \(x\), \(\mu(x) \leq h(x)\mu_1(x)\),
where \(h\) is polynomial on \(\mu\)-average\@.
Distribution \(\mu\) is \emph{weakly dominated by \(\nu\) with respect to \(f\)},
written as \(\mu \preceq_f^{ap} \nu\), if
there exists a distribution \(\mu_1\) such that
\(\mu\) is weakly dominated by \(\mu_1\) and 
\(\nu(y) = f(\mu_1)(y)\) for all \(y \in \mathrm{range}(f)\)\@. 
Reductions defined under these two weaker
requirements are called \emph{ap-time many--one reductions}\@.
%
\apar{3.1-6}
A distributional problem is \emph{many--one complete} for DistNP
(or simply average-case NP-complete)
if it is in DistNP and every other problem in DistNP is 
\(\leq_m^p\)-reducible to it\@. Several distributional NP problems 
under uniform distributions have been shown
to be many--one complete for \allowbreak DistNP~\cite{cj99-02-14,cj99-02-09,cj99-02-21,cj99-02-19}\@.
%

\asubsection{3.2}{Randomized Reductions} \label{s:reduction}
%
\apar{3.2-1}
The notion of many-one reductions has certain limitations\@. 
In particular, it is not suitable for studying completeness of problems 
when ``flat" distributions are presented\@. 
A distribution \(\mu\) is \emph{flat} \cite{cj99-02-09} if
there exists an \(\epsilon > 0\) such that for all \(x\),
\(\mu(x) \leq 2^{-|x|^\epsilon}\)\@. Uniform distributions for
graph problems often turn out to be flat \cite{cj99-02-09,cj99-02-21}\@.
Gurevich \cite{cj99-02-08,cj99-02-09} showed that,
unless nondeterministic exponential time collapses to deterministic
exponential time, no distributional
problems with flat distributions can be complete under ap-time
many--one reductions\@. 
Wang and Belanger \cite{cj99-02-21} further showed
that, without any assumption, a distributional problem with
a flat distribution cannot be complete under ap-time, one-one, and p-honest 
reductions\@.  
%
\apar{3.2-2}
We explain why deterministic reductions would fail:
When instances of the target problem are under a flat distribution,
each instance of approximately the same length will have 
approximately the same weight, and this weight is too small to dominate the 
input distribution\@. So no matter how an instance of the target problem
is selected by an honest
deterministic reduction, the domination property will always
be violated\@. 
%
\apar{3.2-3}
Venkatesan and Levin \cite{cj99-02-17}
showed that by using randomized reductions, one can overcome
the difficulties caused by flat distributions\@.
A randomized reduction is a standard randomized (probabilistic) algorithm 
that transforms one string to another\@.
In \cite{cj99-02-17}, the purpose of using a randomized reduction is to generate 
instances of the target problem with sufficiently large probability\@.
The idea is to supply a random source \(S_x\)
for a reduction \(f\) from \((A,\mu_A)\) to \((B,\mu_B)\) on each instance \(x\)
of \(A\), such that
different random strings
\(s \in S_x\) will produce different instances \(f(x,s)\), and
for all \(s \in S_x\), \(x \in A\) if and only if \(f(x,s) \in B\)\@.
Thus, although for each individual instance \(f(x,s)\) of \(B\), \(\mu_B(f(x,s))\)
may be too small to dominate \(\mu_A(x)\), 
the summation \(\sum_s \mu_B(f(x,s))\) may be 
large enough to meet the domination requirement for distributions\@.
To make this point clearer, let us consider the following special case\@. Let
\(S = \setof{(x,s)}{s \in S_x}\) and for all \(s \in S_x\),
\(|s| \ge |x|\)\@. Assume that the reduction \(f\) is one-one on \(S\) and,
for all \(x\), \(\sum_{s\in S_x}2^{-|s|} = 1\)\@. For a 
particular \(s \in S_x\), \(\mu_B(f(x,s))\) may be too small 
to dominate \(\mu_A(x)\), but \(\sum_{s\in S_x}\mu_B(f(x,s))=
\mu_B(f(x,s))2^{|s|}\) may well be large enough to dominate \(\mu_A(x)\)\@.
Thus, if
\(\mu_A(x)2^{-|s|}\) is dominated by \(\mu_B(f(x,s))\), then we have
\(\mu_A(x) = \sum_{s\in S_x}\mu_A(x)2^{-|s|}\), which is
dominated by \(\sum_{s\in S_x}\mu_B(f(x,s))\), a property
we desire\@.
%
\apar{3.2-4}
Following \cite{cj99-02-17,cj99-02-06,cj99-02-07}, we formulate the notion of 
randomized reductions as follows\@.
For simplicity,
we assume that only unbiased random coins are used in randomizations\@.
Let \({\cal A}\) be a randomized algorithm and \(x\) be an input\@.
We are only interested in sequences \(s\) of random bits 
such that \({\cal A}(x)\) halts using \(s\)\@.
Such a random sequence must be finite\@. 
%
\apar{3.2-5}
We allow a randomized algorithm (for solving a problem) to produce
incorrect outputs on some sequences of 
random bits\@. For example, suppose that a 
randomized algorithm \(\cal A\) computes a reduction from \(A\) to \(B\), 
and suppose that \(\cal A\) on
input \(x\), with \(s\) being the random sequence, produces an output string \(y\)\@.
Then the output \(y\) is incorrect if \(x \in A\) but \(y \not\in B\)\@.
If \(\cal A\) halts on input \(x\) with random sequence \(s\)
and produces a correct output, then \((x,s)\) 
is called a \emph{good} input of \(\cal A\)\@.
%
\apar{3.2-6}
{From} now on, we will be interested only in good inputs\@.
Let \(\cal A\) be a randomized algorithm and \(\mu\) an input distribution
of \(\cal A\)\@.
A \emph{good-input domain} of
\(\cal A\) (with respect to \(\mu\)) is the set of all pairs \((x,s)\) such
that \(\mu(x) > 0\),
\(\cal A\) on input \(x\) halts and produces a correct output, and
\(s\) is the random sequence it generates during the computation\@.
Clearly, \(\cal A\) is deterministic on \((x,s)\) and we may view
\((x,s)\) as the input of \(\cal A\)\@.
If \(\cal A\) computes a function \(f\), then we can view \(f\) as
a deterministic function on \((x,s)\)\@.
If \(\cal A\) is deterministic on \(x\), then \((x,e)\) is
in the good-input domain of \(\cal A\),
where \(e\) denotes the empty string\@.
%
\apar{3.2-7}
Let \(\Gamma\) be a good-input domain of \(\cal A\)\@. Let
\(\Gamma(x) = \setof{s\!}{(x,s) \in \Gamma}\)\@.
We can see that no string in \(\Gamma(x)\)
is a prefix of a different string in \(\Gamma(x)\); otherwise,
the longer string cannot be in \(\Gamma(x)\) as the algorithm stops
before it can be generated\@. 
We say that \(\Gamma(x)\) is \emph{non-rare} \cite{cj99-02-06}
if the rarity function of \(\Gamma\), defined by
\(U_\Gamma(x) = 1/\sum_{s\in\Gamma(x)}2^{-|s|}\) 
if \(\mu(x) >0\) and \(U_{\Gamma}(x)=1\) otherwise,
is polynomial on \(\mu\)-average\@.\footnote{If for all \(x\), \(U_\Gamma(x) = 1\),
then the randomized algorithm produces a correct output with
probability 1\@. For our purpose, we only need to require that
the value of \(U_\Gamma(x)\) be ``reasonable'' in the sense that
\(U_\Gamma\) is polynomial on \(\mu\)-average\@.}
A good-input domain \(\Gamma\) is called \emph{non-rare} if
for all \(x\), \(\Gamma(x)\) is non-rare\@.
%
\apar{3.2-8}
For all \((x,s) \in \Gamma\), let 
\[\mu_\Gamma(x,s) = \mu(x)2^{-|s|}U_\Gamma(x).\]
Here the factor \(U_\Gamma(x)\) is used for normalization
(see Definition 2.8 in \cite{cj99-02-07} on page 955)\@.
%
\begin{alabsubtext}{Definition}{3}{\cite{cj99-02-06,cj99-02-07}}
%\begin{definition} 
Let \({\cal A}\) be a randomized algorithm with input distribution
\(\mu\)\@. 
Then \(\cal A\) runs in time \emph{polynomial on \(\mu\)-average} if 
there is a good-input domain \(\Gamma\) of \(\cal A\)
and an \(\varepsilon > 0\) such that \(\Gamma\) is non-rare, and
\[\sum_{(x,s)\in \Gamma}t^\varepsilon(x,s)|x|^{-1}\mu_\Gamma(x,s) < \infty,\]
where \(t(x,s)\) is the running time of \(\cal A\) on input \(x\) with
random sequence \(s\)\@. 
\end{alabsubtext}
%\end{definition}
%
\apar{3.2-9}
For simplicity, when there is no confusion about the input distribution \(\mu\),
we call a randomized algorithm that runs in time polynomial on \(\mu\)-average
a \emph{randomized ap-time algorithm}\@. 
%
\apar{3.2-10}
The probability that a randomized ap-time algorithm 
\({\cal A}\) on input \(x\) produces a correct output is \(1/U_\Gamma(x)\), 
a value that could be small\@. Blass and Gurevich \cite{cj99-02-06,cj99-02-07} showed
that the algorithm can be iterated to obtain
a correct solution with probability 1 in ap-time, provided that 
the correct output 
can be verified in ap-time\@. For the purpose of iteration, we would like
to require that the good-input domain of the algorithm be
decidable in ap-time with respect to \(\mu_\Gamma\)\@.
In \cite{cj99-02-07}, such a good-input domain is called
\emph{certifiable}\@. 
%
\apar{3.2-11}
Let \((A,\mu)\) be a distributional problem\@. 
Let \({\cal D}_A\) be the set of all (positive and negative) instances of \(A\)\@. 
When \((A,\mu)\) is solvable by a 
randomized algorithm, we may view a good-input domain of the algorithm as
a ``randomized" input domain of \((A,\mu)\)\@. 
Sometimes we would like to refer
to a good-input domain without specifying a randomized algorithm, and
we will call it a \emph{randomized input domain of \((A,\mu)\)}\@.
%
\apar{3.2-12}
Let RAP be the class of distributional problems \((A,\mu)\) for which
there is a randomized ap-time algorithm \({\cal A}\) with a good-input
domain \(\Gamma\) such that
\(\Gamma\) is non-rare, certifiable, and 
for all \((x,s) \in \Gamma\), \(x \in A\) if and only if \({\cal A}(x,s)\) accepts\@.
RAP is an average-case analogue of ZPP\@. \footnote{Clearly, for every set 
\(A \in {\rm ZPP}\) and
every distribution \(\mu\), \((A,\mu) \in {\rm RAP}\)\@. 
We might as well
use AZPP to denote RAP\@. We may also 
define ABPP as analogous to BPP, and use ABPP as a notion of 
\emph{easiness}\@.} 
%
\begin{alabsubtext}{Definition}{4}{\cite{cj99-02-07}} \label {d:random-decision} 
\apar{Definition 4-1}
Let \((A,\mu_A)\) and \((B,\mu_B)\) be distributional 
problems\@. Then \((A,\mu_A)\) is \emph{ap-time randomly
reducible to} \((B,\mu_B)\), denoted by \((A,\mu_A) \leq_r^{ap} (B,\mu_B)\),
if there is a reduction \(f\) such that the following conditions
are satisfied\@.
\begin{enumerate}
\item
The reduction \(f\) is
computable by a randomized algorithm in time
polynomial on \(\mu_A\)-average with a 
good-input domain \(\Gamma_A\)\@.
%
\item \(\Gamma_A\) is non-rare and certifiable\@.
%
\item 
For all \((x,s) \in \Gamma_A\),
\(x \in A\) if and only if \(f(x,s) \in B\)\@.
\item
\(\mu_{\Gamma_A} \preceq_f^{ap} \mu_B\)\@. 
\end{enumerate}
%
\apar{Definition 4-2}
If the reduction \(f\) can be computed by a randomized p-time algorithm,
then \(f\) is called a \emph{randomized p-time reduction}\@.
\end{alabsubtext}
%\end{definition}
%
\apar{3.2-13}
Clearly, deterministic reductions are a special case of randomized reductions
with good inputs \((x,e)\), where \(e\) is the empty string\@.
%
\apar{3.2-14}
The following lemma is straightforward\@. 
%
\begin{alabsubtext}{Lemma}{1}{} \label{l:one-one}
If \(f: \Gamma_A \rightarrow B\) is one-one over \(\Gamma_A\), then 
\(\mu_{\Gamma_A} \preceq_f^{ap} \mu_B\) if and only if
\(\mu_{\Gamma_A} \preceq^{ap} \mu_B \!\circ\! f\)\@.
\end{alabsubtext}
%\end{lemma}
%
\apar{3.2-15}
We will often use the phrase ``via \((f,\Gamma_A)\)" to emphasize the
randomized reduction \(f\) and its non-rare good-input domain \(\Gamma_A\)\@.
%
\begin{alabsubtext}{Lemma}{2}{\rm\bf (\cite{cj99-02-07})}
%\begin{lemma} 
(1) If \((A,\mu_A) \leq_r^{ap} (B,\mu_B)\) and \((B,\mu_B)\) is in
{\rm RAP}, then so is \((A,\mu_A)\)\@.
(2) Randomized ap-time reductions are transitive\@. 
\end{alabsubtext}
%\end{lemma}
%

\asection{4}{Randomized Isomorphisms} \label{s:random}
%
\apar{4-1}
Berman and Hartmanis defined 
two problems \(A\) and \(B\) to be p-isomorphic if there
exists a p-time computable and invertible bijection
\(\phi: {\cal D}_A \rightarrow {\cal D}_B\) such that
\(A \leq^p_m B\) via \(\phi\) and \(B \leq^p_m A\) via \(\phi^{-1}\)\@.
For distributional problems \((A,\mu_A)\) and \((B,\mu_B)\),
Wang and Belanger \cite{cj99-02-21} defined that
\((A,\mu_A)\) and \((B,\mu_B)\)
are p-isomorphic
if there exists a p-time computable and invertible bijection
\(\phi: {\cal D}_A \rightarrow {\cal D}_B\) such that
\((A,\mu_A) \leq_m^p (B,\mu_B)\) via \(\phi\) and 
\((B,\mu_B) \leq_m^p (A,\mu_A)\) via \(\phi^{-1}\)\@.
Polynomial isomorphisms on distributional problems are transitive\@.
%
\apar{4-2}
Let \(\mu\) and \(\nu\) be two distributions\@.
Write \(\mu \approx^p \nu\) if \(\mu\) is dominated by \(\nu\) and
\(\nu\) is dominated by \(\mu\)\@.
Wang and Belanger \cite{cj99-02-21} showed the following p-time equivalent 
of the Cantor-Bernstein-Myhill theorem for distributional problems\@.
%
\begin{alabsubtext}{Theorem}{1}{\cite{cj99-02-21}} \label{t:wb} 
Let \((A,\mu_A) \leq^p_m (B,\mu_B)\) via \(f\), and \((B,\mu_B) \leq^p_m
(A,\mu_A)\) via \(g\), then \((A,\mu_A)\) is p-isomorphic to \((B,\mu_B)\)
if both \(f\) and \(g\) are one-one, length-increasing, p-time computable,
and p-time invertible, and \(\mu_A \approx^p \mu_B \!\circ\! f\) 
(here \(\mu_B\!\circ\! f(x) = \mu_B(f(x))\)) and
\(\mu_B \approx^p \mu_A \!\circ\! g\)\@. 
\end{alabsubtext}
%\end{theorem}
%
\apar{4-3}
Note that if \(f\) is one-one, then
\(\mu \preceq_f^p \nu\) if and only if \(\mu \preceq \nu\!\circ\! f\) \cite{cj99-02-09}\@.
Using Theorem 1, Wang and Belanger \cite{cj99-02-21}
showed that all the known distributional NP
problems that are complete under p-time many--one reductions
are p-isomorphic\@.
%
\apar{4-4}
Let \(\pi_1\) and \(\pi_2\) be functions defined on tuples of strings
such that \(\pi_1\) returns the first element and \(\pi_2\) returns 
the second element\@.
%
\apar{4-5}
Next, we consider how to generalize the notion of isomorphisms
to the setting of randomized reductions\@. 
Let \((A, \mu_A)\) and \((B,\mu_B)\) be two distributional problems\@.
Recall that the notion of isomorphisms under deterministic reductions
is defined to be a bijection between input domains of the underlying
problems\@. Following this framework, we consider
bijections \(\Psi\) between a randomized input domain of
\((A,\mu_A)\) and a randomized input domain of \((B,\mu_B)\)\@. 
Note that a randomized reduction 
takes a random string as input and does not
output one\@. 
This leads us to consider \(\pi_1\!\circ\! \Psi\) and
\(\pi_1\!\circ\! \Psi^{-1}\) as possible reductions; namely,
we would like to transform (encode) each instance of \(A\)
to a unique instance of \(B\) via \(\pi_1\!\circ\! \Psi\), and transform
each instance of \(B\) back to a unique instance of \(A\) via \(\pi_1\!\circ\!
\Psi^{-1}\)\@.
This gives rise naturally 
to the following definition of isomorphism under
randomized reductions\@.
%
\begin{alabsubtext}{Definition}{5}{}
%\begin{definition}
\((A,\mu_A)\) is \emph{randomly isomorphic to} \((B,\mu_B)\), denoted by
\((A,\mu_A) \equiv_r (B,\mu_B)\), if the following conditions hold\@.
\begin{enumerate}
\item There exist randomized input domains \(\Gamma_A\) of \((A,\mu_A)\)
and \(\Gamma_B\) of \((B,\mu_B)\), 
and a bijection
\(\Psi\) between \(\Gamma_A\)
and \(\Gamma_B\) such that \(\Psi\) is ap-time computable on
\(\Gamma_A\) and \(\Psi^{-1}\) is ap-time computable on \(\Gamma_B\)\@.
%
\apar{4-6}
\item Let \(f = \pi_1\!\circ\! \Psi\) and 
\(g = \pi_1 \!\circ\! \Psi^{-1}\)\@.
Then \((A,\mu_A) \leq^{ap}_r (B,\mu_B)\) via \((f,\Gamma_A)\),
and \((B,\mu_B) \leq^{ap}_r (A,\mu_A)\) via \((g,\Gamma_B)\)\@.
\end{enumerate}
\end{alabsubtext}
%\end{definition}
%
\apar{4-7}
Clearly, randomized isomorphisms are transitive\@.
%
\apar{4-8}
Next, we show a randomized ap-time equivalent of the
Cantor-Bernstein-Myhill theorem for distributional problems
as a natural generalization of the
p-time equivalent of the Cantor-Bernstein-Myhill theorem\@.
%
\apar{4-9}
A (partial) function \(f:\Sigma^*\times \Sigma^* \rightarrow \Sigma^*\)
(or \(f:\Sigma^*\times \Sigma^* \rightarrow \Sigma^*\times \Sigma^*\))
is said to be \emph{length-increasing} if 
\(|f(x,y)| > |x|+|y|\) whenever \(f(x,y)\) is defined\@.
%
\apar{4-10}
Let \((A,\mu_A)\) and \((B,\mu_B)\) be two distributional problems\@.
Assume that \((A,\mu_A) \leq^{ap}_r (B,\mu_B)\) via \((f, \Gamma_A)\) and
\((B,\mu_B) \leq^{ap}_r (A,\mu_A)\) via \((g, \Gamma_B)\)\@. 
In view of Theorem 1, we would first require that
\(f\) and \(g\) be one-one, length-increasing, and invertible\@. 
We then would like \(\mu_A\) and \(\mu_B\) to have certain relations
under \(f\) and \(g\)\@. If \(f\) and \(g\) are deterministic many-one
reductions, we have required, as stated in Theorem 1, 
that \(\mu_A \approx^p \mu_B\!\circ\! f\) and
\(\mu_B \approx^p \mu_A\!\circ\! g\)\@. What is needed there is actually
the following two requirements:
\(\mu_B\!\circ\! f \preceq^p \mu_A\) and \(\mu_A\!\circ\! g \preceq^p \mu_B\);
the other parts, namely, \(\mu_A \preceq^p \mu_B\!\circ\! f\) and
\(\mu_B \preceq^p \mu_A \!\circ\! g\), are guaranteed by the one-one reductions\@.
In the setting of randomization, these two requirements may be written
as follows: 
(1) for all \((x,s) \in \Gamma_B\) and
for all \(s' \in \Gamma_A(g(x,s))\): 
\(\mu_{\Gamma_A}(g(x,s),s') \preceq^{ap}\mu_B(x)\);
(2) for all \((x,s) \in \Gamma_A\) and
for all \(s' \in \Gamma_B(f(x,s))\): 
\(\mu_{\Gamma_B}(f(x,s),s') \preceq^{ap} \mu_A(x)\)\@.
We can obtain, as definitions, equivalents of these two statements
without using \(s\) and \(s'\)\@. Since these two statements are
symmetric, we present the equivalent of the first statement
below\@. (The equivalent of the second statement can be obtained similarly\@.)
%
\apar{4-11}
Assume that \((A,\mu_A) \leq^{ap}_r (B,\mu_B)\) via \((f, \Gamma_A)\)\@.
For all \(x \in {\cal D}_A\), let \(l_A(x) = \min\setof{|s|}{s \in \Gamma_A(x)}\)\@.
Then \emph{\(\mu_{\Gamma_A}\) on \(g\) is weakly dominated by}
\(\mu_B\) if for all \(x \in \mathrm{range}(g)\), \(\mu_A(x)2^{-l_A(x)} \preceq^{ap}
\mu_B(\pi_1(g^{-1}(x)))\)\@. 
%
\apar{4-12}
To prove Theorem 2, we would also like to acquire the following
property\@.
%
\begin{alabsubtext}{Definition}{6}{} \label{d:selectable}
Let \(\Gamma\) be a randomized input domain of \((A,\mu_A)\)\@. 
Then \(\Gamma\) is \emph{selectable} if there is a p-time
computable function \(\xi:{\cal D}_A \rightarrow \Sigma^*\)
such that for every \(x \in {\cal D}_A\), \((x,\xi(x)) \in \Gamma\)\@.
The function \(\xi\) is called a \emph{selection function of \(\Gamma\)}\@.
\end{alabsubtext}
%\end{definition}
%
\begin{alabsubtext}{Theorem}{2}{} \label{t:one}
Suppose \((A,\mu_A) \leq_r^{ap} (B,\mu_B)\) via \((f,\Gamma_A)\)
and \((B,\mu_B) \leq_r^{ap} (A,\mu_A)\) via \((g,\Gamma_B)\)\@.
Then \((A,\mu_A) \equiv_r (B,\mu_B)\)
if the following conditions hold\@.
\begin{enumerate}
\item Both \(\Gamma_A\) and \(\Gamma_B\) are certifiable and selectable\@.
%
\item Both \(f: \Gamma_A \rightarrow B\) and \(g: \Gamma_B \rightarrow A\) 
are one-one, length-in\-crea\-sing, and
ap-time invertible\@.
%
\item The distribution \(\mu_{\Gamma_A}\) on \(g\) is weakly
dominated by \(\mu_B\), and \(\mu_{\Gamma_B}\) on \(f\) is weakly
dominated by \(\mu_A\)\@.
\end{enumerate}
\end{alabsubtext}
%\end{theorem}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
\apar{Proof of Theorem 2-1}
By assumption of the reductions, for all \((x,s) \in \Gamma_A\),
\(f(x,s)\) is defined; and, for all \((x,s) \in \Gamma_B\),
\(g(x,s)\) is defined\@. Without loss of generality, assume that,
for \((x,s) \not\in \Gamma_A\), \(f(x,s)\) is not defined, and
for \((x,s) \not\in \Gamma_B\), \(g(x,s)\) is not defined\@.
Hence, \(f\) is a deterministic function on input domain \(\Gamma_A\), and
\(g\) is a deterministic function on input domain \(\Gamma_B\)\@.
%
\apar{Proof of Theorem 2-2}
By assumption, both \(\Gamma_A\) and \(\Gamma_B\) are selectable\@. 
Let \(\xi_A\) and \(\xi_B\) be the p-time computable  
selection functions of \(\Gamma_A\) and
\(\Gamma_B\), respectively\@.
%
\apar{Proof of Theorem 2-3}
Define functions \(F: \Gamma_A \rightarrow \Gamma_B\) and 
\(G: \Gamma_B \rightarrow \Gamma_A\) as follows\@.
\begin{eqnarray}
\forall (x,s) \in \Gamma_A: F(x,s) &=& (f(x,s),\xi_B(f(x,s))) \label{e:1}\\
\forall (x,s) \in \Gamma_B: G(x,s) & = & (g(x,s), \xi_A(g(x,s))) \label{e:2}
\end{eqnarray}
%
\apar{Proof of Theorem 2-4}
Since both \(f\) and \(g\) are one-one and length-increasing,
both \(F\) and \(G\) are one-one and ap-time computable\@.
%
\apar{Proof of Theorem 2-5}
We have 
\begin{eqnarray*}
F^{-1}(x,\xi_B(x)) & = & (\pi_1(f^{-1}(x)),\pi_2(f^{-1}(x))) \\
G^{-1}(x,\xi_A(x)) & = & (\pi_1(g^{-1}(x)),\pi_2(g^{-1}(x))).
\end{eqnarray*}
%
\apar{Proof of Theorem 2-6}
It is easy to see that both
\(F^{-1}\) and \(G^{-1}\) are ap-time computable\@. 
They are also length-decreasing; namely,
\(|F^{-1}(x,s)| < |x|+|s|\) and
\(|G^{-1}(x,s)| < |x|+|s|\)\@. 
Hence, the sets \(R_1,~R_2,~S_1\), and \(S_2\) 
defined below are all ap-time decidable\@.
\begin{eqnarray*}
R_1 &=& \setof{(G\!\circ\! F)^k(x,s)}{k \ge 0, (x,s) \not\in G(\Gamma_B),~\mbox{and}~ (x,s)\in \Gamma_A~\mbox{if \(k=0\)}},\\
R_2 &=& \setof{G\!\circ\! (F\!\circ\! G)^k(x,s)}{k \ge 0,~\mbox{and}~ (x,s)\not\in F(\Gamma_A)}, \\
S_1 &=& \setof{(F\!\circ\! G)^k(x,s)}{k \ge 0, (x,s) \not\in F(\Gamma_A),~\mbox{and}~ (x,s)\in \Gamma_B~\mbox{if \(k=0\)}},\\
S_2 &=& \setof{F\!\circ\! (G\!\circ\! F)^k(x,s)}{k \ge 0,~\mbox{and}~ (x,s)\not\in G(\Gamma_B)}.
\end{eqnarray*}
%
\apar{Proof of Theorem 2-7}
Following the proof given in \cite{cj99-02-05},
we can show that
\(\Gamma_A = R_1 \union R_2\), \(R_1\interset R_2 = 
\emptyset\), and \(\Gamma_B = S_1 \union S_2\), \(S_1\interset S_2 =
\emptyset\)\@. 
Also, for every \((x,s) \in \Gamma_A\),
\((x,s) \in R_1\) if and only if \(F(x,s) \in S_2\), and \((x,s) \in R_2\) 
if and only if \(F(x,s) \in S_1\)\@. Similarly, for every \((x,s)\in\Gamma_B\),
\((x,s) \in S_1\) if and only if
\(G(x,s) \in R_2\), and \((x,s) \in S_2\) if and only if \(G(x,s) \in R_1\)\@.
%
\apar{Proof of Theorem 2-8}
Let, for all \((x,s) \in \Gamma_A\), 
\[\Psi(x,s) = \left\{\begin{array}{ll}
	F(x,s), & \mbox{if \((x,s) \in R_1\)}, \\
	G^{-1}(x,s), & \mbox{if \((x,s) \in R_2\)}.
	\end{array}\right.\]
Then the 
inverse of \(\Psi\) is given by, for all \((x,s) \in \Gamma_B\),
\[\Psi^{-1}(x,s) = \left\{\begin{array}{ll}
	G(x,s), & \mbox{if \((x,s) \in S_1\)},\\
	F^{-1}(x,s), & \mbox{if \((x,s) \in S_2\)}.
	\end{array}\right.\]
The function \(\Psi\) is the desired bijection between \(\Gamma_A\) 
and \(\Gamma_B\)\@.
%
\apar{Proof of Theorem 2-9}
Next, we show that \((A,\mu_A) \leq_r^{ap} (B,\mu_B)\)
via \((\pi_1\!\circ\!\Psi,\Gamma_A)\)\@. (We can similarly
show that \((B,\mu_B) \leq_r^{ap} (A,\mu_A)\) 
via \((\pi_1\!\circ\!\Psi^{-1},\Gamma_B)\)\@.)
%
\apar{Proof of Theorem 2-10}
Let \((x,s) \in \Gamma_A\)\@. 
%
\apar{Proof of Theorem 2-11}
\emph{Case 1:} 
\((x,s) \in R_1\)\@. Then
\(\pi_1\!\circ\!\Psi(x,s) = f(x,s)\)\@. Since by assumption,
\((A,\mu_A) \leq_r^{ap} (B,\mu_B)\) via \((f,\Gamma_A)\), 
we have \(x \in A\) if and only if \(f(x,s) \in B\) and 
\(\mu_{\Gamma_A} \preceq^{ap}_f \mu_B\)\@. Since \(f\) is one-one over
\(\Gamma_A\), it follows from Lemma 1 that
\(\mu_{\Gamma_A} \preceq^{ap}\mu_B\!\circ\! f\)\@.
By the definition of \(F\), we have \(\pi_1\!\circ\! \Psi(x,s) = f(x,s)\)\@.
Thus, we have \(x \in A\) if and only if 
\(\pi_1\!\circ\!\Psi(x,s) \in B\), and 
\(\mu_{\Gamma_A}\preceq^{ap}\mu_B\!\circ\! (\pi_1\!\circ\!\Psi)\)\@.
Since \(\pi_1\!\circ\!\Psi\) is one-one, we have that
\(\mu_{\Gamma_A}\) is weakly dominated by \(\mu_B\)
with respect to \(\pi_1\!\circ\!\Psi\)\@.
%
\apar{Proof of Theorem 2-12}
\emph{Case 2:} \((x,s) \in R_2\)\@. Then \(g^{-1}(x)\) is defined and it
follows from Equation (2) that
\(\pi_1\!\circ\!\Psi(x,s) = \pi_1 \!\circ\! G^{-1}(x,s)
= \pi_1(g^{-1}(x))\)\@. 
Since \(g^{-1}(x)\) is defined,
\((\pi_1\!\circ\! g^{-1}(x),\pi_2\!\circ\! g^{-1}(x)) 
\in \Gamma_B\)\@. 
So we have 
\(\pi_1\!\circ\! g^{-1}(x) \in B\) if and only if \(g(\pi_1\!\circ\! g^{-1}(x),
\pi_2\!\circ\! g^{-1}(x)) \in A\)\@. 
Since \(g(\pi_1\!\circ\! g^{-1}(x),
\pi_2\!\circ\! g^{-1}(x)) = x\),
this implies that \(x \in A\) if and only if 
\(\pi_1\!\circ\!\Psi(x,s) \in B\)\@.
By Condition 3 in the statement of the theorem,
\(\mu_A(x)2^{-l_A} \preceq^{ap}\mu_B(\pi_1(g^{-1}(x)))\),
where \(l_A = \min\setof{|s|}{s \in \Gamma_A(x)}\)\@. Since
\(|s| \geq l_A\), we have \(\mu_{\Gamma_A}(x,s) = \mu_A(x)2^{-|s|} 
\leq \mu_A(x)2^{-l_A}\),
which implies that \(\mu_{\Gamma_A}\) is weakly dominated by 
\(\mu_B\!\circ\! (\pi_1\!\circ\! \Psi)\)\@. Again, since \(\pi_1\!\circ\!\Psi\) is
one-one, we have that \(\mu_{\Gamma_A}\) is weakly dominated by
\(\mu_B\) with respect to \(\pi_1\!\circ\!\Psi\)\@.
This completes the proof\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%\end{proof}
%
\apar{4-13}
Built on rich structures of complete sets, 
Berman and Hartmanis \cite{cj99-02-05} obtained a sufficient condition
under which reductions are guaranteed to be p-time invertible\@.
In particular, let \(A\) be a set for which
two p-time computable functions \(S_A(\cdot,\cdot)\) and \(D_A(\cdot)\)
exist with the following properties:
(1) \((\forall x, y)[S_A(x,y) \in A ~\mbox{if and only if}~ x \in A]\), and
(2) \((\forall x,y)[D_A(S_A(x,y)) = y]\)\@.
Then if \(f\) is any p-time reduction of some set \(C\) to \(A\), 
the map \(f'(x) = S_A(f(x),x)\) is one-one and invertible in p-time
and reduces \(C\) to \(A\)\@. An easy proof 
shows that all the known, standard
NP-complete sets do satisfy these two properties 
\cite{cj99-02-05}\@. It follows
from the p-time equivalent of the Cantor-Bernstein-Myhill theorem 
for (worst-case) decision problems that
all the known standard NP-complete
problems are p-isomorphic\@. 
%
\apar{4-14}
For distributional problems, however, the reductions need to
be easily invertible \emph{and} preserve the probability distributions\@.
Unfortunately, no functions such as \(S_A\) and \(D_A\) above are known that
preserve the probabilities in a useful way\@.
For \(w \in A\), we would need the probability of \(D_A(w)\)
to depend on the probability function associated to the arbitrary
set \(C\), and hence to an undetermined probability function\@.
So to use Theorem 2, we will 
investigate individual reduction used in each completeness proof\@.
Fortunately, this task can often be accomplished by using the existing
completeness proofs, with some minor modifications if necessary\@.
Using Theorem 2, we can show that all the known 
average-case NP-complete problems are indeed randomly isomorphic\@.
%

\asection{5}{Isomorphism Proofs} \label{s:main}
%
\apar{5-1}
Levin \cite{cj99-02-14} (see also \cite{cj99-02-09}) 
showed that any p-time computable distribution 
on string \(x\) is dominated by a uniform distribution on strings whose length
is polynomially related to \(|x|\)\@. 
Based on that, Wang and Belanger proved the following Distribution
Controlling Lemma \cite{cj99-02-21}\@.
%
\begin{alabsubtext}{Lemma}{3}{Distribution Controlling Lemma} \label{l:6} 
Let \(\mu\) be a p-time computable distribution\@.
If there exists a polynomial \(p\) such that
for all \(x\), \(\mu(x) > 2^{-p(|x|)}\),
then there is a total, one-one, p-time computable and p-time invertible
function \(\alpha\!:\Sigma^* \rightarrow \Sigma^*\) such that for all \(x\),
\(4 \cdot 2^{-|\alpha(x)|} \leq \mu(x) < 20 \cdot 2^{-|\alpha(x)|}\)\@.
\end{alabsubtext}
%\end{lemma}
%
\apar{5-2}
We first use distributional halting problems as an example
of obtaining an isomorphism proof\@.
%

\asubsection{5.1}{Distributional Halting}
%
\apar{5.1-1}
Let \(M_1, M_2, \dots\) be a fixed enumeration of 
nondeterministic Turing machines in which the index
\(i\) is a binary integer that codes up the symbols, states, and
transition table of the \(i\)-th Turing machine \(M_i\)\@. \\
%
\apar{5.1-2}
{\sc Distributional Halting (Version 1)} \\
\emph{Instance}\@. Binary strings \(i\), \(x\), and a unary notation \(1^n\)
representing positive integer
\(n\), where \(i\) is a positive integer in binary form\@.
%
\apar{5.1-3}
\emph{Question}\@. Does \(M_i\) accept \(x\) within \(n\) steps?
%
\apar{5.1-4}
\emph{Distribution}\@. Uniform; namely,
the distribution on instance \((i,x,1^n)\) is proportional to
\(2^{-(l+m)}l^{-2}m^{-2}n^{-2}\), where \(l = |i|\) and \(m = |x|\)\@. \\
%
\apar{5.1-5}
{\sc Distributional Halting (Version 2)}\\
\emph{Instance}\@. Binary strings \(i\), \(x\), and \(t\), where
\(i\) is a positive integer\@. 
%
\apar{5.1-6}
\emph{Question}\@. Does \(M_i\) accept \(x\) within \(|t|\) steps?
%
\apar{5.1-7}
\emph{Distribution}\@. Uniform; namely, 
the distribution on instance \((i,x,t)\) is proportional to
\(2^{-(l+m+n)}l^{-2}m^{-2}n^{-2}\),
where \(l=|i|\), \(m=|x|\), and \(n = |t|\)\@. \\
%
\apar{5.1-8}
Let \((K,\mu_K)\) and \((K',\mu_{K'})\)
denote the halting problem version 1 and version 2, respectively\@.
\((K,\mu_K)\) is is complete for DistNP under
p-time many--one reductions \cite{cj99-02-09,cj99-02-04,cj99-02-21}\@.
\((K',\mu_{K'})\) (note that \(\mu_{K'}\) 
is flat) is complete for DistNP under randomized p-time reductions
\cite{cj99-02-09,cj99-02-20}\@.
%
\begin{alabsubtext}{Theorem}{3}{} \label{t:halting}
\((K,\mu_K) \equiv_r (K',\mu_{K'})\)\@.
\end{alabsubtext}
%\end{theorem}
%
\begin{alabsubtext}{Proof of Theorem}{3}{}
\prooffontshape
%\begin{proof}
\apar{Proof of Theorem 3-1}
Let \(\Gamma_K = \setof{(y,s)\!}{y=(i,x,1^n)~{\rm and}~|s| = n}\)\@.
Then \(\Gamma_K\) is certifiable, non-rare 
(the rarity function \(U_\Gamma(x) = 1\)), and selectable\@.
For a given string \(y=(i,x,1^n)\), let \(h\) be a function that pads the
program \(i\) such that 
\(h\) is p-time computable, p-time invertible, 
\(|h(i)| > |i|+O(1)\), and \(M_{h(i)} = M_i\)\@.
Let \(h(i) = j\); then \(|h^{-1}(j)| = |j|-O(1)\)\@.
For all \((y,s) \in \Gamma_K\), let 
\(f(y,s) = (h(\pi_1(y)), \pi_2(y), s)\)\@.
Then \(f\) is one-one, length-increasing, p-time computable, and
p-time invertible\@. 
Hence, for all \((y,s) \in \Gamma_K\), we have 
\(y \in K\) if and only if \((\pi_1(y), \pi_2(y), s) \in K'\)
if and only if \((h(\pi_1(y)), \pi_2(y), s) \in K'\)\@.
This implies that \(y \in K\) if and only if \(f(y,s) \in K'\)\@.
By definition, \(\mu_{\Gamma_K}(y,s) = \mu_K(y)2^{-|s|}\), which
is proportional to \(\mu_{K'}(f(y,s))\)\@. Hence,
\(\mu_{\Gamma_K}(y,s)\) is dominated by \(\mu_{K'}(f(y,s))\)\@.
Thus,
\((K,\mu_K) \leq_r^{ap} (K',\mu_{K'})\) via \((f,\Gamma_K)\)\@.
%
\apar{Proof of Theorem 3-2}
Next, we show that \((K',\mu_{K'})\) is polynomially reducible 
to \((K,\mu_K)\) via a length-increasing, one-one, deterministic reduction\@.
We can see that
\((K',\mu_{K'}) \leq^p_m (K,\mu_K)\) by a reduction that maps 
\((i,x,s)\) to \((h(i),x,1^{|s|})\)\@.
But this reduction is not one-one and so cannot be used\@.
We will construct a different reduction using a standard technique 
as shown in \cite{cj99-02-21}\@.
Note that \(\mu_{K'}\) satisfies
the hypothesis of the Distribution Controlling Lemma\@.
So there is a total, one-one, p-time computable, and
p-time invertible function \(\alpha\) such that for all \(y \in {\cal D}_{K'}\),
\(4 \cdot 2^{-|\alpha(y)|} < \mu_{K'}(y) < 20 \cdot 2^{-|\alpha(y)|}\)\@.
Let \(M\) be a nondeterministic
Turing machine \(M\) that accepts \(K'\) in polynomial time\@.
Define a Turing machine \(M'\) as follows: On binary input \(w\), 
if \(\alpha^{-1}(w)\) is defined, then \(M'\)
simulates \(M\) on \(\alpha^{-1}(w)\) and rejects otherwise\@.
So for all \(y \in {\cal D}_{K'}\), 
\(M\) accepts \(y\) if and only if 
\(M'\) accepts \(\alpha(y)\)\@.
It is easy to see that \(M'\) on input \(\alpha(y)\) is bounded in 
polynomial time, and we call it \(p(|y|)\)\@.
%
\apar{Proof of Theorem 3-3}
Let \(i\) be a program such that \(M' = M_i\)\@. Let 
\(g(y) = (i,\alpha(y),1^{p(|y|)})\)\@. Then
\(g\) is one-one, length-increasing, p-time computable,
and p-time invertible\@.
By construction, \(y \in K'\) if and only if \(g(y) \in K\)\@.
Moreover, \(\mu_K \!\circ\! g(y) \approx^p 2^{-|\alpha(y)|} \approx^p
\mu_{K'}(y)\)\@. Thus, we have
\((K',\mu_{K'}) \leq^p_m (K,\mu_K)\) via \(g\)\@.
%
\apar{Proof of Theorem 3-4}
Conditions 1 and 2 of Theorem 2 regarding \(\Gamma_{K'}\)
are obviously satisfied\@. 
To complete this direction, we need only show that Condition 3
of Theorem 2 holds\@.
For this purpose, we view function \(g\) as a function defined on 
\(\Gamma_{K'} = \setof{(y,e)\!}{y\in{\cal D}_{K'}}\) by \(g(y,e) = g(y)\)\@.
Let \(z \in \mathrm{range}(g)\)\@. Then \(z = g(y)\) for some \(y \in {\cal D}_{K'}\)\@.
Hence, we have \(\mu_K(z) \approx^p 
\mu_{K'}\!\circ\! (g^{-1}(z))\)\@. 
Let \(l_K = \min\setof{|s|}{ s\in \Gamma_K(z)}\)\@.
Then \(\mu_K(z)2^{-l_K} < \mu_K(z)\)\@. This implies that
\(\mu_K(z)2^{-l_K}\) is dominated by
\(\mu_{K'}(\pi_1(g^{-1}(z)))\)\@. The first statement of
Condition 3 of Theorem 2 is
therefore satisfied\@.
We now show that the second statement of Condition 3 is also satisfied\@.
Let \(y = (i,x,s) \in \mathrm{range}(f)\)\@.
Then \(f^{-1}(y) = (y', s)\), where \(y' = (h^{-1}(i),x,1^{|s|})\)\@.
Hence,
\(\pi_1(f^{-1}(y)) = (h^{-1}(i),x,1^{|s|})\)\@. Since \(|h^{-1}(i)| = |i|-O(1)\),
this implies that
\(\mu_{\Gamma_{K'}}(y)\) is dominated by
\(\mu_K(\pi_1(f^{-1}(y)))\)\@.
%
\apar{Proof of Theorem 3-5}
We have therefore verified that all the conditions of Theorem 2
are satisfied, and so \((K,\mu_K) \equiv_r (K',\mu_{K'})\)\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 3}}
\end{alabsubtext}
%\end{proof}
%

\asubsection{5.2}{Distributional Tiling and Graph Spot Coloring}
%
\apar{5.2-1}
A tile is a square with a symbol on each corner\@. Tiles 
may not be rotated or turned over\@.
We assume that there are infinitely many copies of each type of tile\@. 
By a tiling of an \(n\times n\) square we mean an arrangement of
\(n^2\) tiles to cover the entire square so that the symbols 
on the touching corners of adjacent tiles are the same\@. 
%
\apar{5.2-2}
{\sc Distributional Tiling} \\
\emph{Instance}\@. 
A finite set of tiles \(T\), 
a unary notation \(1^n\) for a positive integer \(n\),
and a sequence \(S = s_1s_2\dots s_k\) (\(k \le n\)) 
of tiles that match each other; that is,
the symbols on the touching corners of
\(s_i\) and \(s_{i+1}\) are the same\@.
%
\apar{5.2-3}
\emph{Question}\@. Can \(S\) be extended to
tile an \(n\times n\) square using tiles from \(T\)?
%
\apar{5.2-4}
\emph{Distribution}\@. Uniform; namely, the distribution is 
proportional to \(\mathrm{Pr}[T]n^{-2}\mathrm{Pr}[S]\), 
where \(\mathrm{Pr}[T]\) is the probability of choosing \(T\),\footnote{One
can use one's favorite distribution to select \(T\) or simply
select it uniformly at random among binary strings, since \(T\) is
coded in binary\@.} and 
\(\mathrm{Pr}[S]\) is the probability of choosing \(S\)\@. \(S\) is chosen by first
choosing \(k\) at random with probability \(1/n\), then
choosing the first tile \(s_1\) at random from \(T\),
and choosing the \(s_i\) (\(i>1\)) sequentially and uniformly at 
random from those tiles in \(T\) that match \(s_{i-1}\)\@. 
%
\apar{5.2-5}
Levin \cite{cj99-02-14} showed that the distributional tiling problem 
is average-case NP-complete under a deterministic reduction\@.
Gurevich \cite{cj99-02-09} provided a detailed proof for tiles with 
marked edges, where each edge of a tile is marked with a symbol;
in the tiling of a square, symbols on the touching edge of
adjacent tiles are the same\@. Belanger and Wang \cite{cj99-02-02,cj99-02-21} presented 
a simpler proof\@. Distributional tiling with marked corners and with marked
edges are polynomially isomorphic\@. 
%
\apar{5.2-6}
We are interested in the following variant of
distributional tiling on tiles with marked corners\@.
First, the set of tiles \(T\) is fixed; so
\(T\) is no longer a component of an instance\@. Second,
in the \(S\) component of an instance, 
the two corners at the same side of a tile have the same binary digit\@.
The first tile in \(S\) has a special symbol on its lower-left corner\@.
It is easy to see that there exists \(T\), 
denote it by \({\cal T}\), 
such that this variant of
distributional tiling is p-isomorphic to
the standard distributional tiling\@. 
(For example, we can construct \({\cal T}\) based on a fixed Turing machine
that accepts \(K\)\@.)
Denote by \(({\cal T},\mu_{\cal T})\) this average-case NP-complete
variant\@.
%
\apar{5.2-7}
Venkatesan and Levin \cite{cj99-02-17} studied the following
edge-coloring problem for directed graphs (digraphs, in short), 
where nodes are labeled and
may have self-loops\@. For convenience, we assume that 
self-loops with single direction and self-loops with double directions are
distinct\@.
(This assumption can be used to simplify proofs\@.)
Let \(G\) be such a digraph\@.
An edge of \(G\) may be colored or left blank 
(i.e., uncolored), with a constant
number of colors\@.
A \emph{spot}
in a colored digraph is a 3-node subgraph with induced
colored edges (including self-loops if there are any) 
and the nodes unlabeled\@. 
It is easy to see that there are only a constant number of different 
spots\@.
The \emph{coloration} \(C(G)\) of \(G\) consists of the set of all spots 
induced from the colored graph \(G\) and the number of blank edges\@. 
%
\apar{5.2-8}
Write \(f(n) \sim g(n)\) if \(\lim_{n\rightarrow \infty} f(n)/g(n) = 1\)\@. \\
%
\apar{5.2-9}
{\sc Distributional Graph Spot Coloring} \\
\emph{Instance}\@. A digraph \(G\) of \(n\) nodes, a set \(C\) 
of spots, and a unary notation \(1^k\) for a positive integer \(k\),
where \(k < {n \choose 2}\)\@. 
%
\apar{5.2-10}
\emph{Question}\@. Can \(G\) be colored
such that \(C(G) = (C',k)\) and \(C' \subseteq C\)?
(If so, we then say that \(G\) is colorable\@.)
%
\apar{5.2-11}
\emph{Distribution}\@. Uniform: First choose a positive integer \(n\) with
probability \(\Theta(n^{-2})\), then randomly and
independently choose a directed graph of \(n\)
nodes with uniform probability \(4^{-{n \choose 2}}3^{-n} \sim 2^{-n^2}\), 
a set of spots with probability \(\Theta(1)\), the number of
blank edges \(k\) with probability \(\Theta(n^{-2})\)\@.
Hence, the probability distribution
is proportional to \(n^{-4}2^{-n^2}\),
which is flat\@.
%
\apar{5.2-12}
Let \((E,\mu_E)\) denote 
the distributional graph spot-coloring problem\@.
Venkatesan and Levin \cite{cj99-02-17} (a slightly different proof was given
in \cite{cj99-02-16}) showed that \((E,\mu_E)\) is
average-case NP-complete under a randomized 
reduction\@.\footnote{What would be the 
minimum number of colors that can make the distributional graph
spot coloring problem complete for DistNP? That is an interesting
question\@. It was claimed that 20 colors \cite{cj99-02-17}, or
even much fewer colors \cite{cj99-02-16}, are sufficient\@.}
%
\begin{alabsubtext}{Theorem}{4}{} \label{t:tiling}
\(({\cal T},\mu_{\cal T}) \equiv_r (E,\mu_E)\)\@.
\end{alabsubtext}
%\end{theorem}
%
\begin{alabsubtext}{Proof of Theorem}{4}{}
\prooffontshape
%\begin{proof}
\apar{Proof of Theorem 4-1}
For a large part, we follow a proof given in \cite{cj99-02-17},
showing that distributional graph spot-coloring is average-case NP-complete\@.
To arrive quickly to the point showing why
a randomized isomorphism exists,
we will omit proofs to certain lemmas;
all of the missing proofs can be found in \cite{cj99-02-17,cj99-02-16}\@.
%
\apar{Proof of Theorem 4-2}
A \emph{tournament}
is an acyclic (except for self-loops) complete
digraph\@. Any tournament contains a Hamiltonian path; there is
a deterministic p-time algorithm that starts from the
node with smallest label and finds a Hamiltonian
path uniquely (see, e.g., \cite{cj99-02-15})\@.
Let \(k = |T|\)\@. 
Let \(t_1, t_2, \dots, t_k\) be a Hamiltonian path of a
tournament \(T\) found in this way\@.
Define the code for a node \(u\)
to be the binary string of length \(2|T|\) of the form
\(c(t_1,u)c(u,t_1) \dots c(t_k,u)c(u,t_k)\), where
\(c(u,v) = 1\) if \(u \rightarrow v\) and 0 otherwise \cite{cj99-02-01}\@.
So \(T\) determines the code for \(u\) uniquely\@.
%
\apar{Proof of Theorem 4-3}
We now construct a randomized reduction \(f\) from \(({\cal T}, \mu_{\cal T})\) to
\((E,\mu_E)\)\@. Let \(X = (1^n,S)\) (\(|S| < n\)) 
be an instance of \(({\cal T},\mu_{\cal T})\)\@. 
%
\apar{Proof of Theorem 4-4}
The reduction \(f\) first partitions 
\(\{1, \dots, 2n^2+k-1\}\) at random into disjoint
sets \(T,~L,~U\), with \(|T| = k = \lceil 2\log n\rceil+1\), \(|L| = n^2\),
and then randomly adds edges to generate
a random graph of \(2n^2+k-1\) nodes\@.
Let \(r(n)\) be the number of
random bits required in this random process\@. (In \cite{cj99-02-17}, it indicates
that \(r(n) = 5n^4\) is sufficient\@.)  
Since there are \(2^{(2n^2+k-1)^2}\) many graphs and we need extra
random bits to generate a partition,
\(r(n) > (2n^2+k-1)^2\)\@.
Clearly, a partition and a 
graph can be uniquely constructed in time polynomial of
\(n\) when \(r(n)\) random bits are given\@.
%
\apar{Proof of Theorem 4-5}
Among the random graphs so generated, we are particularly interested
in the ones that satisfy the following conditions\@.
%
\begin{enumerate}
\item \(T\) is a tournament\@. 
\item 
\(T\) is the set of all nodes with double-direction self-loops
and \(L\) is the set of all nodes with single-direction self-loops\@.
(Self-loops are used to enforce the graph structure and the color
pattern\@.)
\item Every node in \(L\union U\) is connected to every node in \(T\)\@.
\item All unlooped nodes (i.e., nodes in \(U\)) have distinct codes 
with respect to \(T\)\@.
\item Let \(v_1,v_2, \dots, v_{|U|}\) be the nodes in \(U\) in
the decreasing order of codes with respect to \(T\)\@.
If the symbol of the right side of the \(i\)-th tile of \(S\) is 0, then
\(v_i \rightarrow v_{i+1}\) is the only edge between \(v_i\) and \(v_{i+1}\); 
if the symbol is 1, then \(v_i \leftarrow v_{i+1}\) is the only edge\@.
If \(i \geq |S|\), then there are no edges between \(v_i\) and \(v_{i+1}\)\@.
\end{enumerate}
%
\apar{Proof of Theorem 4-6}
Note that the last condition above gives an encoding of \(S\) in the graph\@.
Also, in \cite{cj99-02-17}, it was required that \(T\) be the unique \(k\)-node
tournament\@. In our construction, all nodes in \(T\) are with double-direction
self-loops, and no other nodes have such self-loops\@. This makes
\(T\) unique\@. 
Let \(G\) denote the resultant graph; we call it a \emph{tiling
graph}\@. Venkatesan and Levin \cite{cj99-02-17} 
showed that there are sufficiently many tiling graphs\@.
%
\begin{alabsubtext}{Lemma}{4}{\cite{cj99-02-17}} \label{l:randomgraph} 
The probability that \(G\) is a tiling graph
is at least \(\Omega(n^{-d})\) for some constant \(d>1\)\@.
\end{alabsubtext}
%\end{lemma}
%
\apar{Proof of Theorem 4-7}
Let \(\Gamma_{\cal T}(X) = 
\setof{s}{|s| = r(n)~\mbox{and \(s\) produces a tiling graph \(G\) from \(X\)}}
\)\@. 
Then \(\Gamma_{\cal T} = \setof{(X,s)}{s \in \Gamma_{\cal T}(X)}\) is a 
good-input domain of \(f\)\@. It follows from Lemma 4
that \(U_{\Gamma_{\cal T}}(X) = \Omega(n^{-d})\) and so
\(\Gamma_{\cal T}\) is non-rare\@. Also, given a random sequence \(s\),
it is easy (in p-time) to check whether the graph generated by \(s\)
is a tiling graph\@.
%
\apar{Proof of Theorem 4-8}
Based on the structures of \(G\),
Venkatesan and Levin \cite{cj99-02-17}
(see also \cite{cj99-02-16})
constructed a color specification \((C,b)\) in time
polynomial of \(n\), where \(C\) is a finite
set of spots and \(b = O(\sqrt{n})\) such that 
the following lemma holds true\@.
%
\begin{alabsubtext}{Lemma}{5} {\cite{cj99-02-17}} \label{l:main}
For every random string \(s \in \Gamma_{\cal T}(X)\), 
\(X\) is a positive instance 
of distributional tiling \(\cal T\)
if and only if the graph \(G\) produced by \(f(X,s)\) 
is colorable under the color specification \((C,b)\)\@. Moreover, 
the tiling can be constructed in polynomial time from a coloring\@.
\end{alabsubtext}
%\end{lemma}
%
\apar{Proof of Theorem 4-9}
The desired reduction \(f(X,s)\), for \((X,s) \in \Gamma_{\cal T}\),
is the digraph \(G\) as described above, plus the color specification
\((C,b)\)\@. 
%
\apar{Proof of Theorem 4-10}
It is easy to see that \(f\) is one-one, length-increasing, 
and p-time computable on input \((X,s) \in \Gamma_{\cal T}\)\@. 
To see that
\(\mu_{\Gamma_{\cal T}}(X,s)\) is dominated by \(\mu_E(f(X,s))\),
we note that 
\(\mu_E(f(X,s))\) is proportional to \((2n^2+k-1)^{-4}2^{-(2n^2+k-1)^2}\),
and \(\mu_{\Gamma_{\cal T}}(X,s) = \mathrm{Pr}[X]2^{-|s|}
\leq 2^{-|s|} = 2^{-r(n)}\), where \(\mathrm{Pr}[X]\) is the probability
distribution of \(X\)\@. Since \(-r(n) < -(2n^2+k-1)^2\),
\(\mu_{\Gamma_{\cal T}}(X,s)\) is dominated by \(\mu_E(f(X,s))\)\@. 
%
\apar{Proof of Theorem 4-11}
We now show that \(f\) is p-time invertible\@.
Given a tiling graph \(G\), we can easily identify
\(T\), \(L\), and \(U\) by checking whether a node has a 
double-direction self-loop, a single-direction self-loop, or no self-loop\@.
Our task is
therefore to find \(S\) that is embedded in \(G\)\@.
{From} \(T\), we
can obtain distinct codes for nodes in \(U\) and so \(S\) can be
identified\@. The partition \(T\), \(L\), and \(U\),
and the edges of \(G\) reveal the random string \(s\) that generates
the graph\@.
Clearly, this algorithm can be carried out in time polynomial of \(n\)\@.
This algorithm also shows that \(\Gamma_{\cal T}\) is selectable\@.
%
\apar{Proof of Theorem 4-12}
Next, we consider the other direction\@.
Since \(\mu_E\) satisfies the hypothesis of the Distribution Controlling Lemma,
it has been shown in \cite{cj99-02-21} 
that \((E,\mu_E) \leq^p_m ({\cal T},\mu_{\cal T})\) 
via a deterministic 
reduction \(g\) that is one-one, p-time computable, and
p-time invertible\@. Moreover, \(\mu_E \approx^p \mu_{\cal T}\!\circ\! g\)\@.
So for every
\(X \in \mathrm{range}(g)\), where \(X = (1^n,S) \in {\cal D}_{\cal T}\), and for
every \(s \in \Gamma_{\cal T}(X)\),
\(\mu_{\Gamma_{\cal T}}(X,s) < \mu_{\cal T}(X)\), which is
dominated by \(\mu_E(g^{-1}(X))\)\@.
This shows that the first part of Condition 3 of Theorem 2
is satisfied\@.
%
\apar{Proof of Theorem 4-13}
We verify that the second part of Condition 3 of Theorem 2 
is also satisfied\@.
First, we may view \(g\) as a function defined on \(\Gamma_E = 
\setof{(Y,e)}{Y \in {\cal D}_E}\) by \(g(Y,e) = g(Y)\)\@. Let \(Y \in \mathrm{range}(f)\), then
\(Y = (G,(C,b)) = f((1^n,S),s)\) for a unique \(((1^n,S),s) \in \Gamma_{\cal T}\), 
where \(|S| < n\), and \(|G| = 2n^2+k-1\), where \(|G|\) denotes the number of
nodes in \(G\)\@.
Hence,
\(\mu_{\Gamma_E}(Y,e) = \mu_E(Y) \approx^p |G|^{-4}2^{-|G|^2}\)\@.
Since \(\mu_{\cal T}(1^n,S)\) is proportional to \(n^{-2}c^{-|S|}\) 
for some constant
\(c\) (\(c \leq |{\cal T}|\)) and \(|S| < n\), we have that
\(\mu_{\Gamma_E}(Y,e)\) is dominated by \(\mu_{\cal T}(1^n,S) = \mu_{\cal T}
(\pi_1(f^{-1}(Y)))\)\@. 
%
\apar{Proof of Theorem 4-14}
{From} Theorem 2, this completes the proof\@.
{\nopagebreakbeginpar\markendlst{Proof of Theorem 4}}
\end{alabsubtext}
%\end{proof}
%

\asubsection{5.3}{Distributional Matrix Transformation}
%
\apar{5.3-1}
A square matrix \(X\) is called \emph{unimodular} if all entries in \(X\) are
integers and its determinant \(\det(X) = 1\)\@. 
Let \(\mathrm{SL}_2(\integers)\) denote the
set of \(2 \times 2\) unimodular matrices\@.
Define the size of a unimodular matrix \(X\), denoted by \(|X|\),
to be the length
of the binary representation of the maximal absolute value
of its entries\@. 
%
\apar{5.3-2}
The distributional matrix transformation problem 
deals with linear transformations on \(2 \times 2\)
unimodular matrices\@.
A \emph{linear transformation} of \(\mathrm{SL}_2(\integers)\) is
a function \(T:\mathrm{SL}_2(\integers)\rightarrow
\mathrm{SL}_2(\integers)\) such that \(T(\sum X_i) = \sum T(X_i)\)
whenever all the \(X_i\) and \(\sum X_i\) are unimodular matrices\@.
(Note that in general, \(\mathrm{SL}_2(\integers)\) is not closed under
addition\@.) 
A linear transformation of \(\mathrm{SL}_2(\integers)\)
can be represented by a \(4 \times 4\) integer
matrix, and it is decidable in polynomial time whether
a given \(4\times 4\) integer matrix represents a linear transformation
of \(\mathrm{SL}_2(\integers)\) \cite{cj99-02-09,cj99-02-07}\@.
%
\apar{5.3-3}
Let \(T\) be a linear transformation and let \(M(T)\) be its
\(4 \times 4\) integer matrix representation\@.
Define the \emph{size} of \(T\)
to be the length of the largest absolute value (in the binary notation) of 
entries in \(M(T)\)\@. Gurevich \cite{cj99-02-09} (see also \cite{cj99-02-07})
showed that the uniform
distribution of \(T\) among all linear transformations of size \(l\) is
\(\Theta(l^{-1}2^{-2l})\)\@.
%
\apar{5.3-4}
{\sc Distributional Matrix Transformation}\\
\emph{Instance}\@. A unimodular matrix \(X\), a finite set \(S\) of linear
transformations of unimodular matrices, and a unary notation \(1^n\)
for a positive integer \(n\)\@. 
%
\apar{5.3-5}
\emph{Question}\@. Does a linear transformation \(T\) exist,
where \(T = T_1 \!\circ\! T_2 \!\circ\! \dots \!\circ\! T_k\), \(k \le n\),
\(T_i \in S\), such that \(T(X)\) is the identity matrix?
%
\apar{5.3-6}
\emph{Distribution}\@.
The three components are chosen randomly and independently\@. 
The integer
component \(n\) is chosen with respect to the default uniform
distribution
\(1/n^2\)\@. The unimodular component \(X\) is chosen with
probability \(|X|^{-2}2^{-2|X|}\)\@.
Linear transformations are chosen with respect to the
uniform distribution on transformations of the same size\@.
Finally, the probability
of \(S\) is proportional to the product of the probabilities
of the members in \(S\)\@. \\
%
\apar{5.3-7}
Let \((T,\mu_T)\) denote the distributional matrix transformation problem\@.
Blass and Gurevich \cite{cj99-02-07} showed that \((T,\mu_T)\)
is average-case NP-complete under a randomized reduction\@.
Based on that we can show
the following result, and we leave the proof to the reader\@.
%
\begin{alabsubtext}{Theorem}{5}{}
%\begin{theorem}
\((K,\mu_K) \equiv_r (T,\mu_T)\)\@.
\end{alabsubtext}
%\end{theorem}
%
\apar{5.3-8}
We can also show that the distributional matrix representability problem
with flat distribution \cite{cj99-02-18} is randomly isomorphic to
\((K,\mu_K)\)\@. The reader is referred to \cite{cj99-02-18} for a definition
of the problem, and we again leave the isomorphism proof to the reader\@. \\

\asection{Acknowledgments}{}
I am grateful to Jay Belanger for several interesting discussions and for
proofreading an early draft of this paper\@.  I thank the two anonymous
referees for several useful suggestions\@.

%
\end{articletext}
%
\begin{articlebib}
\bibliographystyle{alpha}
\bibliography{cj99-02}
\end{articlebib}

\end{document}