On polynomial-time relation reducibility (Q2364655)

Equivalence problems (such as graph isomorphism, Boolean formula equivalence, etc.) can be viewed as equivalence relations \(R \subseteq \Sigma^* \times \Sigma^*\) for some finite alphabet \(\Sigma\). Let \(R,S \subseteq \Sigma^* \times \Sigma^*\) be equivalence relations. Then \(R\) is said to be \textit{polynomial-time relation reducible} to \(S\) (written \(R \leq_R S\)) if there is a function \(f: \Sigma^* \to \Sigma^*\) computable in polynomial time such that \((x,y)\) in \(\Sigma^* \times \Sigma^*\) is in \(R\) if and only if \((f(x),f(y))\) is in \(S\). This requirement is stronger than in the definition of standard polynomial-time reducibility, where the reduction function depends on pairs \((x,y)\) in \(\Sigma^* \times \Sigma^*\); for relation reducibility, the reduction function \(f\) depends just on the projections \(x,y \in \Sigma^*\). Relation reducibility was introduced under the name \textit{kernel reducibility} in [\textit{L. Fortnow} and \textit{J. A. Grochow}, Inf. Comput. 209, No. 4, 748--763 (2011; Zbl 1238.68061)] and studied under the name \textit{strong equivalence reducibility} in [\textit{S. Buss} et al., J. Symb. Log. 76, No. 4, 1381--1402 (2011; Zbl 1248.03060)]. The authors prove several fundamental properties of relation reducibility, mostly demonstrating structural richness of \(\leq_R\) on the class of computable equivalence relations. An infinite ascending chain and an infinite antichain with respect to \(\leq_R\) are constructed. The main result proved in the article states that the partial order of polynomially computable sets of natural numbers can be embedded into the quasi-order \(\leq_R\). More precisely, let \(\mathrm{id} \subseteq \Sigma^* \times \Sigma^*\) denote the identity relation and \(\mathrm{E}_{\lambda} \subseteq \Sigma^* \times \Sigma^*\) be a relation such that \((x,y)\) is in \(\mathrm{E}_{\lambda}\) if and only if \(|x| = |y|\). Let us denote the set of all polynomially computable sets of natural numbers by \(P_{\mathbb N}\). Then there is a mapping \(\varphi: P_{\mathbb N} \to 2^{\Sigma^* \times \Sigma^*}\) such that \(\varphi(X)\) is an equivalence relation satisfying \(\mathrm{E}_{\lambda} \leq_R \varphi(X) \leq_R \mathrm{id}\) for each \(X\) in \(P_{\mathbb N}\), and \(X \subseteq Y \iff \varphi(X) \leq_R \varphi(Y)\) for each \(X\), \(Y\) in \(P_{\mathbb N}\). Properties of relation reducibility on special classes of finitary equivalence relations are studied as well.