preliminaries.tex

%% preliminaries.tex - mathematical definitions of kernel reductions
%%
%% Copyright 2010, 2011, 2012, 2014, 2015 Jeffrey Finkelstein.
%%
%% This LaTeX markup document is made available under the terms of the Creative
%% Commons Attribution-ShareAlike 4.0 International License,
%% https://creativecommons.org/licenses/by-sa/4.0/.
\section{Preliminaries}
\label{sec:preliminaries}

The set of natural numbers (including $0$) is denoted $\mathbb{N}$, the set of integers is denoted $\mathbb{Z}$, and the set of positive integers is denoted $\mathbb{Z}^+$.

If $f\colon S\to T$ is a well-defined function and $S'\subseteq S$, then \defn{$f$ restricted to the domain $S'$} is the function $f'\colon S'\to T$ defined by $f'(x)=f(x)$ for all $x\in S'$.
We denote this restricted function on a smaller domain by $f|_{S'}$.
The \emph{image of $S'$}, denoted $f(S')$, is defined by $f(S') = \{f(s) \, | \, s \in S'\}$.

In this paper, $\Sigma$ denotes the binary alphabet $\{0, 1\}$.
$\Sigma^*$ is the set of all binary strings over the alphabet $\Sigma$ and $\Sigma^{\leq n}$ is the set $\lb w\in\Sigma^* \st |w|\leq n \rb$.
The empty string will be denoted by $\lambda$.
If $\sigma\in\Sigma$ then $\sigma^k$ is the string consisting of $k$ concatenated copies of the symbol $\sigma$.
If $x$ and $y$ are elements of $\Sigma^*$, then we denote by $\pair{x}{y}$ the \defn{pairwise encoding} of $x$ and $y$, which is itself an element of $\Sigma^*$.
In this paper, we will assume the reasonable pairwise encoding defined by $\pair{x}{y}=x_1x_1x_2x_2\cdots x_{|x|}x_{|x|}01y_1y_1y_2y_2\cdots y_{|y|}y_{|y|}$ for all $x$ and $y$ in $\Sigma^*$.
As usual, a \defn{language} over an alphabet $\Sigma$ is a subset of $\Sigma^*$.
The \defn{complement} of a language $L$ is $\Sigma^*\backslash L$, and is denoted $\overline{L}$.

The complexity classes $\P$, $\NP$, $\FP$ (polynomial-time computable functions), $\SKP$, $\PKP$, $\DKP$, and $\PSPACE$ have the usual definitions.
The set of words accepted by a Turing machine $M$ is denoted $L(M)$.
The \defn{complement} of a complexity class $\mathcal{C}$ is the set of complements of languages in $\mathcal{C}$, and is denoted $\coC$.

We say a Turing machine $M$ is a \defn{polynomially clocked Turing machine} if the description of $M$ includes a positive integer $k$ such that $M$ halts within time $kn^k$ on all inputs of length $n$.

If $L_1$ and $L_2$ are languages, we say that \defn{$L_1$ many-one reduces to $L_2$} if there exists a computable function $f$ such that $w \in L_1$ if and only if $f(w) \in L_2$.
We denote this by $L_1 \mornt L_2$.
If $f$ is computable in polynomial time, we denote this by $L_1 \mor L_2$.
%% If $L_1 \mor L_2$ and $L_2 \mor L_1$, we say that $L_1$ and $L_2$ are \defn{equivalent under polynomial-time many-one reductions}, and denote this by $L_1\moe L_2$.

A set $R \subseteq \Sigma^* \times \Sigma^*$ is an \defn{equivalence relation on $\Sigma^*$} if $R$ satisfies the following three properties.
\begin{itemize}
\item (reflexivity) For all $x \in \Sigma^*$, $(x,x)\in R$.
\item (symmetry) For all $x,y\in \Sigma^*$, $(x,y)\in R$ implies $(y,x)\in R$.
\item (transitivity) For all $x,y,z\in \Sigma^*$, $(x,y)\in R$ and $(y,z)\in R$ implies $(x,z)\in R$.
\end{itemize}
An equivalence relation $R$ can be encoded as a language by taking the pairwise encoding of each pair in $R$.
In this way we can study the computational complexity of classes of languages which represent equivalence relations.
In this paper we will abuse notation and write $\pair{x}{y}\in R$ for an equivalence relation $R$ on $\Sigma^*$, but what we really mean is $(x,y)\in R$ and $\pair{x}{y}\in L_R$, the language on the alphabet $\Sigma$ induced by $R$.

The \defn{equivalence class} of $x$ with respect to an equivalence relation $R$ on $\Sigma^*$ is $\lb y\in \Sigma^* \st (x,y)\in R \rb$.
It is denoted $[x]_R$, or if the context is clear, simply $[x]$.
Each element $x\in \Sigma^*$ is in exactly one equivalence class, so the equivalence classes of an equivalence relation on $\Sigma^*$ provide a partition of $\Sigma^*$.
Conversely, a partition of $\Sigma^*$ induces an equivalence relation on $\Sigma^*$ in which a pair of elements is in the relation if they are in the same block of the partition.

A \defn{complete invariant} for an equivalence relation $R$ on $\Sigma^*$ is a function $f\colon \Sigma^* \to \Sigma^*$ such that for each $x$ and $y$ in $\Sigma^*$, we have $(x, y) \in R$ if and only if $f(x) = f(y)$.
(A \emph{canonical form} for an equivalence relation is a complete invariant satisfying the additional requirement that $f(x) \in [x]_R$; canonical forms, though important, do not appear in this paper.)
%% (In other words, a complete invariant is a kernel reduction from $R$ to the equality relation.)
In \autoref{sec:definitions} we will define generalizations of the complete invariant which accept as input an additional witness to the equivalence of $x$ and $y$.

\defn{$\PEq$} is the class of equivalence relations for which membership can be decided by a Turing machine running in deterministic polynomial time.
\defn{$\NPEq$} is the class of equivalence relations for which membership can be decided by a Turing machine running in non-deterministic polynomial time.
In other words, $\PEq$ is the set of (languages induced by) equivalence relations which are in \P, and $\NPEq$ is the set of (languages induced by) equivalence relations which are in \NP.
In general, the class \defn{$\CEq$} is the class of languages induced by equivalence relations which are in the complexity class $\mathcal{C}$.
As usual, $\PEq\subseteq\NPEq$.
%\defn{$\Ker$} is the class of equivalence relations which have a polynomial time computable complete invariant.

We now require a natural notion of reduction among equivalence relations.
If $R$ and $S$ are equivalence relations on $\Sigma^*$, we say $R$ \defn{kernel reduces to} $S$ if there exists a computable $f\colon\Sigma^*\to\Sigma^*$ such that $\forall x,y\in\Sigma^*$, $\pair{x}{y}\in R\iff \pair{f(x)}{f(y)}\in S$.
We denote this by $R\krnt S$.
If $f$ is computable in polynomial time, then we say $R$ \defn{polynomial-time kernel reduces to} $S$ and use the notation $R\kr S$.

Notice the difference between a kernel reduction and a many-one reduction: a kernel reduction maps $\pair{x}{y}\in R$ to $\pair{f(x)}{f(y)}\in S$, whereas a many-one reduction maps $\pair{x}{y}\in R$ to $f(\pair{x}{y})\in S$, for some polynomial-time computable function $f$.
Informally, a function which computes a many-one reduction has access to both $x$ and $y$ but a function which computes a kernel reduction has access to only one of $x$ and $y$ at a time.
Since it is more restrictive, a kernel reduction induces a many-one reduction (namely the function $\pair{x}{y} \mapsto \pair{f(x)}{f(y)}$).
Still, kernel reductions compose just as many-one reductions do, and $\NPEq$ is closed under polynomial-time kernel reductions, allowing us to adapt existing complexity theoretic analysis to the study of complexity of equivalence relations.

As an analog to polynomial-time many-one completeness in \NP, we define a similar notion of completeness under polynomial-time kernel reductions in \NPEq.
An equivalence relation $S$ is \defn{\NPEq-hard} if for all $R\in\NPEq$, $R\kr S$.
If $S$ is also in \NPEq, then it is \defn{\NPEq-complete}.
If $S$ is \NPEq-complete, we sometimes say that $S$ is \defn{complete under $\kr$ reductions in \NPEq}.
Generally, an equivalence relation $S$ is \defn{$\CEq$-hard} if for all $R\in\CEq$, $R\kr S$, and \defn{$\CEq$-complete} if it is additionally in $\CEq$.