# On approx-preserving P- and A-reducibilities

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

• 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 Oct 10 '15 at 8:24
• 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 Oct 10 '15 at 8:36