Are there arbitraraly hard worst case problems with polynomial time average case complexity?

Question

For example, are there worst case Decidable(but non primitive recursive or other insane time complexity)problems that have a polynomial average case complexity? If so Are there undecidable worst case problems that have polynomial time average case algorithms? Is there a limit on the arithmetical hierarchy where there cannot be Polynomial time average case algorithms past a certain point? Is there an upper bound on the worst case complexity for an algorithm to be polynomial in the average case?

If they exist, What are some examples of practical problems with a worst case complexity of worse then PSPACE? that have polynomial time average case algorithms? I think computing a groebner basis would be an example of this(it is doubly exponential in the worst case, but im pretty sure in the average case it isn't super bad based on the fact that it is actually used for stuff in practice)

Answer 1

Sure. Let $L_0$ be a hard language (decidable but not primitive recursive, or whatever) and $L_1$ be in $P$. Define

$$L = \{ 1^n || x : x \in L_0, |x|=n \in \mathbb{N} \} \cup \{ w||x : x \in L_1, |w|=|x|=n \in \mathbb{N}, w \ne 1^n \}.$$

Then the average-case complexity of $L$ (under an appropriate uniform distribution) is polynomial, like $L_1$, but its worst-case complexity is hard, like $L_0$.