This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$. Can we generalize this to the theory of average-case complexity?
What evidence can be brought for/against the idea that any $(S, X) \in \mathsf{sampNP}$ is either in $\mathsf{sampP}$ or $\mathsf{sampNP}$-complete? Here $S$ is a language and $X$ is a distribution: a probabilistic polynomial time algorithm which generates strings of length $n$ given input $1^n$
A theorem by Shoening allows generalization of Ladner's theorem to many cases. However, it doesn't cover the current question for two reasons
The first reason is that we're considering classes of distributional problems rather than classes of languages. This feels like a technicality that can be dealt with by generalizing Shoening's theorem
The second reason is that the result crucially depends on the fact that $\mathsf{P}$ is recursively presentable. On the other hand $\mathsf{sampNP} \cap \mathsf{sampP}$ doesn't seem to be recursively presentable. For any unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$ we can recursively present distributional problems in $\mathsf{sampNP}$ for which the probability of error decreases at least as fast as $n^{-f(n)}$ however there seems to be no way of allowing the condition to hold for some $f$. This would be possible if there was a recursive enumeration of unbounded functions $f_i: \mathbb{N} \rightarrow \mathbb{N}$ s.t. for any computable unbounded function $g: \mathbb{N} \rightarrow \mathbb{N}$, there is $i$ s.t. $f_i$ grows slower than $g$. However there is no such enumeration as can be seen by a diagonalization argument
The second reason feels to me like a conceptual breakdown of Shoening's reasoning for this case
Imagliazzo's proof of Ladner's theorem fails even more spectacularly in this setting since the padding employed there yields a language whose density diminishes with superpolynomial speed and therefore is trivially in $\mathsf{sampP}$. At least this is so for natural $\mathsf{sampNP}$-complete problems since their distributions are close to uniform