Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I try to figure out a redundant power of two-sided error randomized Karp - reduction.

It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-reduction to coRP (in case of promise problem).

Without delving into details it make sense that the combination of the one - sided error probability of the reduction and the one-sided error probability of coRP leads to two-sided error probability of BPP. Of course the proof of that is not so intuitive.

The question it is possible by two-sided error randomized Karp-reduction to reduce BPP to some constant set in P? In the light of the power of one - sided randomized Karp - reduction, it make sense that two-sided randomized Karp - reduction is strong enough to reduce BPP to constant set, but how to show it formally?

Addendum:

BPP is the set of the problems that is solvable in polynomial time by two-sided error randomized algorithm, so as a result of two - sided error randomized algorithm we will get some output, them the problem in BPP can be reduced to problem P by two-sided error randomized Karp - reduction in sense that reduction is allowed to make error on both sides. Does it mean that two - sided error randomized reduction will justify the two-sided error that was made by the algorithm in solving the problem in BPP?

share|improve this question

1 Answer 1

We can think of a BPP algorithm $A$ for a language $L$ as accepting two inputs, the real input $x$ and a random string $r$, whose length is polynomial in $x$. Now take the Boolean circuit evaluation problem, which is P-complete. Since $A(x,r) \in P$, we can reduce $A$ to this problem, substituting random $r$. Then if $x \in L$ then the reduction yields a YES instance with probability at least $2/3$, and if $x \notin L$ then it yields a NO instance with probability at least $2/3$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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