what is "one-to-one reduction from a function f to another function g"

Question

I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it.

An excerpt from the paper. "Recall that a one-to-one reduction from a function $f$ to another function $g$ is a triple of polynomial time computable functions ($\alpha$, $\beta$, $\gamma$) such that:

1. For all $x$ in the domain of $f$ we have $y=f(x)$ if and only if $g(\alpha(x))=\beta(y)$
2. For all $x$ in the domain of $f$, let $w=\alpha(x)$. Then we have $g(w)=z$ if and only if $f(x)=\gamma(z)$. "

Any reference for the formal definiton of the so-called "one-to-one reduction" is appreciated. Thanks.

Answer 1

The definition is composed of two parts. First, we want a reduction from $f$ to $g$. That's a way of computing $f$ given an oracle to $g$. This reduction is formed by two polytime functions $\alpha,\gamma$ which are used in the following way: $f(x) = \gamma(g(\alpha(x))$.

Second, we want the reduction to be one-to-one. That explains the if-and-only-if in (2). Moreover, for some reason we want an efficient one-to-one right-inverse $\beta$ of $\gamma$, satisfying $y = \gamma(\beta(y))$. The function $\beta$ can be used to answer the following question: what value of $g$ corresponds to a given value of $f$? (In contrast, $\gamma$ tells us what value of $f$ corresponds to a given value of $g$.) Why this is need will be apparent from the way the paper uses $\beta$.

The actual properties stated in the definition are slightly weaker (you want the function to be one-to-one only for values which actually occur in the formulas), but this is the gist of it.

Answer 2

If it helps, there is a formal definition of one-one reducibility on page 80 of "Theory of Recursive Functions and Effective Computability" (PDF here).

Answer 3

Following is my own understanding, which may be wrong. Thanks a lot for the comments.

The one-to-one reduction mentioned in the question is just another formulation of parsimonious reduction which applied to build #P-completeness. The following definition is from "Computational Complexity - A Conceptual Perspective" by Odede Goldreich.

Definition 6.17 (parsimonious reductions): Let $R,R'\in\mathcal{PC}$ and let $g$ be a Karp-reduction of $S_R = \{x \mid R(x)\neq\emptyset\}$ to $S_{R'} = \{x \mid R'(x)\neq \emptyset\}$, where $R(x) = \{y\mid (x,y)\in R\}$ and $R'(x) = \{y\mid (x,y)\in R'\}$. We say that $g$ is parsimonious (with respect to $R$ and $R'$) if for every $x$ it holds that $|R(x)| = |R'(g(x))|$. In such a case we say that $g$ is a parsimonious reduction of $R$ to $R'$.

So the triple $(\alpha,\beta, \gamma)$ in the paper actually defines the transition $g$ in terms of $\alpha$.