2
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ 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? $\endgroup$ – Kaveh May 24 '12 at 18:03
  • $\begingroup$ @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. $\endgroup$ – Peng Zhang May 24 '12 at 18:30
  • 1
    $\begingroup$ 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.) $\endgroup$ – Radu GRIGore May 25 '12 at 6:57
  • 1
    $\begingroup$ I think this question should have moved to cs.stackexchange by now. $\endgroup$ – Tayfun Pay Jun 6 '12 at 18:08
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jun 7 '12 at 1:27
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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$.

enter image description here

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jun 6 '12 at 16:33
  • $\begingroup$ @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? $\endgroup$ – Peng Zhang Sep 17 '12 at 19:52
  • 4
    $\begingroup$ (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? $\endgroup$ – Tsuyoshi Ito Sep 17 '12 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.