Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider two decision problems A and B.
We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A.
Now, let's say it is known that the worst case instances of A reduce to the average case instances of A.
Does it imply the same worst-to-average-case reduction for B?
If not, what are some known counterexamples, considering standard problems/complexity classes?
Let $A$ be any decidable problem, and let $B$ be the following encoding of the halting problem: $$ B = \{(\langle T_1 \rangle, \langle T_2 \rangle) : T_1 = T_2 \text{ and } T_1 \text{ halts on the empty input}\}. $$ Since $A$ is decidable, it can be reduced to $B$, even in polynomial time. But there are natural probability distributions under which $B$ is easy on average.
