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)


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

  • $\begingroup$ 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. $\endgroup$ – Colin McQuillan Oct 10 '15 at 8:24
  • $\begingroup$ 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 ? $\endgroup$ – XORwell Oct 10 '15 at 8:36

Your Answer

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

Browse other questions tagged or ask your own question.