# Question on worst-to-average-case reductions

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?

• Interesting question. It is not clear what you mean by "average-case" instances though -- average case is a certain running time $f(n)$, so I guess you mean instances that are solved in a range of running times close to $f(n)$?
– 6005
Dec 13, 2021 at 20:35

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.