computer-sciencecomplexity-theorycomputation-theoryrandomized-algorithm

If A is in RP and there is a polynomial time reduction from B to A then B in RP?


I think it's true because you can reduce B to A and then run the probabilistic algorithm of A and if we got a reject then it's also a reject for B and at least half of the time if the input is in A we would get an accept which means that at least half of the time if the input is in B we would get an accept. So B is in RP, but I'm not sure.

What happens if the reduction is the other way around? If A is in RP and there is a polynomial time reduction from A to B, then is B in RP?


Solution

  • Reduction from B to A:

    There's a catch. What if all instances of B happen to map to an instance of A that rejects? :)

    This can happen, because B might still have over 50% true instances that accept, but which are just not in the image of your reduction.

    Reduction from A to B:

    As for your second question, consider this: We can reduce A to the halting problem as follows:

    1. Run our RP algorithm for a.
    2. If the answer is yes, return yes. Otherwise, go into an infinite loop.

    Does this mean the halting problem is in RP? :)