<p>If it helps, there is a formal definition of one-one reducibility on page 80 of "Theory of Recursive Functions and Effective Computability" (<a href="http://www-2.dc.uba.ar/materias/azar/bibliografia/Rogers1987TheoryofRecursiveFunctions.pdf" rel="nofollow">PDF here</a>).</p>

CC BY-SA 3.0
2013-09-20T18:35:19.377Z
2013-09-20T18:35:19.377Z
Anna Melzer
<p>The definition is composed of two parts. First, we want a <em>reduction</em> 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))$.</p>

<p>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 <em>efficient</em> 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$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-09-21T00:32:13.437Z
2013-09-21T00:32:13.437Z
Yuval Filmus
<p>Following is my own understanding, which may be wrong. Thanks a lot for the comments.</p>

<p>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 "<a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html" rel="nofollow noreferrer">Computational Complexity - A Conceptual Perspective</a>" by Odede Goldreich.</p>

<blockquote>
  <p><strong>Definition 6.17</strong> (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 <em>parsimonious</em> (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 <em>parsimonious reduction of $R$ to $R'$.</em></p>
</blockquote>

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

<p><img src="https://i.sstatic.net/x7UfC.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2012-06-06T16:33:24.560Z
You are right in that the term _one-to-one reduction_ defined in the paper is related to parsimonious reductions, but it is not a rephrasing.  It seems that you have difficulty understanding the definition stated in the question.  If your real question is “What does the definition of ‘one-to-one reductions’ in this paper mean?” then you may want to ask it on cs.stackexchange.com.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-17T19:52:48.663Z
@TsuyoshiIto Well, I though it was a well-known terminology in TCS. That paper is definitely theoretical, as well as the lemma I asked here. So I don't think this is a wrong place to post. Am I?
Peng Zhang
CC BY-SA 3.0
2012-09-17T22:43:51.600Z
(1) This website cstheory.stackexchange.com is a place for _research-level_ questions in theoretical computer science.  Given that the definition which you quoted from the paper is straightforward (in the sense that it means what it says, without the need for any prior knowledge), I do not think that “What does this definition mean?” is a research-level question.  (2) Which lemma are you talking about?
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-05T18:16:16.030Z
2013-09-21T02:53:28.747Z
2013-09-21T02:53:28.747Z
Peng Zhang
<p>I am reading a paper called "<a href="http://people.csail.mit.edu/azar/wp-content/uploads/2012/04/RationalProofsApril262012.pdf" rel="nofollow">Rational Proof</a>". It mentioned the following one-to-one reduction. I cannot google an introduction of it. </p>

<p>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:</p>

<ol>
<li>For all $x$ in the domain of $f$ we have $y=f(x)$ if and only if $g(\alpha(x))=\beta(y)$</li>
<li>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)$.
"</li>
</ol>

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

CC BY-SA 3.0
2012-05-24T18:03:45.887Z
it helps if you draw a diagram: $f:A\to B$, $g:A'\to B'$, $\alpha:A \to A'$, $\beta:B \to B'$, and $\gamma: B' \to B$. The first condition says the diagram (without $\gamma$) commutes, the second condition says the diagram (without $\beta$) commutes. The one-to-one reduction is normally defined between sets not functions, this one deals with reductions between functions. Have you check the first reference of the paper: Eric W. Allender and Klaus W. Wagner, "Counting
hierarchies: Polynomial time and constant depth
circuits", 1990?
Kaveh
CC BY-SA 3.0
2012-05-24T18:30:07.880Z
@Kaveh: Thank you so much. I did draw a diagram, but in a different way which confused me more. The term "reduction" I came into before is actually a function. Now, it is a triple of functions.
I did not check the first reference, because I thought the mentioned one-to-one reduction is irrelevant to Counting Hierarchy. Rightnow, CH is far beyond me. I heared about Polynomial Hierarchy yesterday.
Peng Zhang
CC BY-SA 3.0
2012-05-24T18:40:45.620Z
@Kaveh: I am still not clear about benefit of rule 1. Normall, if we have a reduction from A to B, we say we can use the power of B to solve A. In the reduction in the question, rule 2 seems sufficient to make sure that we can use function $g$ to calculate $f(x)$. What's the benefit of rule 1?
Peng Zhang
CC BY-SA 3.0
2012-05-25T06:57:43.660Z
From what you quote I understand that $f$ one-to-one reduces to $g$ iff (2) there exist functions $\alpha$ and $\gamma$ such that $f=\gamma\circ g\circ\alpha$ and (1) $\gamma$ is a bijection. Without condition (1) you could one-to-one reduce any function $f$ to the constant function $0$, for example. (Warning: I think this is the idea, but I was rather careless with checking it.)
Radu GRIGore
CC BY-SA 3.0
2012-05-25T14:29:52.280Z
@Radu, 1. $\beta \circ f = g \circ \alpha$ and 2. $f=\gamma \circ g\circ \alpha$, combining the two one gets $f = \gamma \circ \beta \circ f$, which means $\gamma \circ \beta$ is identity over the range of $f$. The idea, I guess, is the following: not only $f$ reduces to $g$, but also their outputs correspond one-to-one, if you want to count the number of possible outputs for $f$ you can count the number of possible outputs for $g$ (over the range of $\alpha$).
Kaveh
CC BY-SA 3.0
2012-05-26T18:10:00.050Z
@RaduGRIGore I think you're missing something: if we ignore (1) and take only (2), (2) still does not allow reducing to a constant function. If $g(w) = 0$ for all $w$, then $z$ is always $0$ and it's impossible that $\gamma(z) = \gamma(0) = f(x)$ for all $x$ (unless $f$ is also a constant function, of course).
Sasho Nikolov
CC BY-SA 3.0
2012-06-06T18:08:26.760Z
I think this question should have moved to cs.stackexchange by now.
Tayfun Pay
CC BY-SA 3.0
2012-06-07T01:27:31.497Z
On surface, this question asks for a prior reference to the notion used in the linked paper, and it is fine on cstheory.stackexchange.com in my opinion.  However, as I wrote in a comment to OP’s answer, OP may want to ask a different question which is more suitable on cs.stackexchange.com.
Tsuyoshi Ito
<cc.complexity-theory><reference-request><terminology><reductions>
what is "one-to-one reduction from a function f to another function g"
Peng Zhang
# what is "one-to-one reduction from a function f to another function g"

(Asked by: username_0 on 2012-05-24)

I am reading a paper called "[Rational Proof](http://people.csail.mit.edu/azar/wp-content/uploads/2012/04/RationalProofsApril262012.pdf)". 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.

**Tags:** cc.complexity-theory, reference-request, terminology, reductions
> **Comments:**
> **username_1**: it helps if you draw a diagram: $f:A\to B$, $g:A'\to B'$, $\alpha:A \to A'$, $\beta:B \to B'$, and $\gamma: B' \to B$. The first condition says the diagram (without $\gamma$) commutes, the second condition says the diagram (without $\beta$) commutes. The one-to-one reduction is normally defined between sets not functions, this one deals with reductions between functions. Have you check the first reference of the paper: Eric W. Allender and Klaus W. Wagner, "Counting hierarchies: Polynomial time and constant depth circuits", 1990?  
> **username_0**: @Kaveh: Thank you so much. I did draw a diagram, but in a different way which confused me more. The term "reduction" I came into before is actually a function. Now, it is a triple of functions. I did not check the first reference, because I thought the mentioned one-to-one reduction is irrelevant to Counting Hierarchy. Rightnow, CH is far beyond me. I heared about Polynomial Hierarchy yesterday.  
> **username_0**: @Kaveh: I am still not clear about benefit of rule 1. Normall, if we have a reduction from A to B, we say we can use the power of B to solve A. In the reduction in the question, rule 2 seems sufficient to make sure that we can use function $g$ to calculate $f(x)$. What's the benefit of rule 1?  
> **username_2**: From what you quote I understand that $f$ one-to-one reduces to $g$ iff (2) there exist functions $\alpha$ and $\gamma$ such that $f=\gamma\circ g\circ\alpha$ and (1) $\gamma$ is a bijection. Without condition (1) you could one-to-one reduce any function $f$ to the constant function $0$, for example. (Warning: I think this is the idea, but I was rather careless with checking it.)  
> **username_1**: @Radu, 1. $\beta \circ f = g \circ \alpha$ and 2. $f=\gamma \circ g\circ \alpha$, combining the two one gets $f = \gamma \circ \beta \circ f$, which means $\gamma \circ \beta$ is identity over the range of $f$. The idea, I guess, is the following: not only $f$ reduces to $g$, but also their outputs correspond one-to-one, if you want to count the number of possible outputs for $f$ you can count the number of possible outputs for $g$ (over the range of $\alpha$).  
> **username_3**: @RaduGRIGore I think you're missing something: if we ignore (1) and take only (2), (2) still does not allow reducing to a constant function. If $g(w) = 0$ for all $w$, then $z$ is always $0$ and it's impossible that $\gamma(z) = \gamma(0) = f(x)$ for all $x$ (unless $f$ is also a constant function, of course).  
> **username_4**: I think this question should have moved to cs.stackexchange by now.  
> **username_5**: On surface, this question asks for a prior reference to the notion used in the linked paper, and it is fine on cstheory.stackexchange.com in my opinion.  However, as I wrote in a comment to OP’s answer, OP may want to ask a different question which is more suitable on cs.stackexchange.com.  

---

## 3 answers

### Answer by username_6 on 2013-09-20. Score: 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](http://www-2.dc.uba.ar/materias/azar/bibliografia/Rogers1987TheoryofRecursiveFunctions.pdf)).


---

### Answer by username_7 on 2013-09-21. Score: 2

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 by username_0 on 2012-06-05. Score: 2

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](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html)" 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$.

![enter image description here](https://i.sstatic.net/x7UfC.jpg)

> **Comments:**
> **username_5**: You are right in that the term _one-to-one reduction_ defined in the paper is related to parsimonious reductions, but it is not a rephrasing.  It seems that you have difficulty understanding the definition stated in the question.  If your real question is “What does the definition of ‘one-to-one reductions’ in this paper mean?” then you may want to ask it on cs.stackexchange.com.  
> **username_0**: @TsuyoshiIto Well, I though it was a well-known terminology in TCS. That paper is definitely theoretical, as well as the lemma I asked here. So I don't think this is a wrong place to post. Am I?  
> **username_5**: (1) This website cstheory.stackexchange.com is a place for _research-level_ questions in theoretical computer science.  Given that the definition which you quoted from the paper is straightforward (in the sense that it means what it says, without the need for any prior knowledge), I do not think that “What does this definition mean?” is a research-level question.  (2) Which lemma are you talking about?  

---

