2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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)$? $\endgroup$
    – 6005
    Dec 13, 2021 at 20:35

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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