<p>Let $X$ and $Y$ be two NPO problems. 
Let $(f,g)$ be a reduction between $X$ and $Y$,
in particular, assume that $(f,g)$ is both P-reduction <em>and</em> A-reduction, 
i.e., </p>

<p>there exist two poly-time  computable functions $c_1,c_2 :(1, +\infty)\cap \mathbb{Q}\mapsto (1, +\infty)\cap \mathbb{Q}$ such that:</p>

<p>$R_B(f(x),y)\leq r \Rightarrow R_A(x, g(x,y))\leq c_2(r)$ (A-reduction) </p>

<p>and</p>

<p>$R_B(f(x),y)\leq c_1(r) \Rightarrow R_A(x, g(x,y))\leq r$ (P-reduction) </p>

<p>Then, can you prove that $c_1$ is invertible and that $c_1=c_2^{-1}$ is always the case ?</p>

<p>(I am reading a paper which asserts that this is always the case, but I don't see it true...) </p>

CC BY-SA 3.0
2015-10-10T08:24:22.803Z
This doesn't hold as stated. For example with a trivial reduction ($X=Y$ and $f(x)=x$ and $g(x,y)=y$, so $R_A=R_B$) we can take $c_1(r)=(1+r)/2$ and $c_2(r)=2r$, which are not inverses.
Colin McQuillan
CC BY-SA 3.0
2015-10-10T08:36:24.773Z
Yeah, I agree that there exist counter-examples... ok, at this point a natural question is: is there a natural rephrasing (concerning the bijectivity of $c()$ ) of the statement which makes it to hold ?
XORwell
<ds.algorithms><np-hardness><approximation-algorithms><approximation-hardness>
On approx-preserving P- and A-reducibilities
XORwell
# On approx-preserving P- and A-reducibilities

(Asked by: username_0 on 2015-10-10)

Let $X$ and $Y$ be two NPO problems.
Let $(f,g)$ be a reduction between $X$ and $Y$,
in particular, assume that $(f,g)$ is both P-reduction *and* A-reduction,
i.e.,

there exist two poly-time computable functions $c\_1,c\_2 :(1, +\infty)\cap \mathbb{Q}\mapsto (1, +\infty)\cap \mathbb{Q}$ such that:

$R\_B(f(x),y)\leq r \Rightarrow R\_A(x, g(x,y))\leq c\_2(r)$ (A-reduction)

and

$R\_B(f(x),y)\leq c\_1(r) \Rightarrow R\_A(x, g(x,y))\leq r$ (P-reduction)

Then, can you prove that $c\_1$ is invertible and that $c\_1=c\_2^{-1}$ is always the case ?

(I am reading a paper which asserts that this is always the case, but I don't see it true...)

**Tags:** ds.algorithms, np-hardness, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: This doesn't hold as stated. For example with a trivial reduction ($X=Y$ and $f(x)=x$ and $g(x,y)=y$, so $R_A=R_B$) we can take $c_1(r)=(1+r)/2$ and $c_2(r)=2r$, which are not inverses.  
> **username_0**: Yeah, I agree that there exist counter-examples... ok, at this point a natural question is: is there a natural rephrasing (concerning the bijectivity of $c()$ ) of the statement which makes it to hold ?  

---

## 0 answers

