MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Does this question still make sense for other "average case" complexity classes like AvgP, DistP, and HeurP? I'm getting these from, which incidentally doesn't list sampP. – Sam Hopkins Dec 28 '12 at 18:49
@SamHopkins : I'm using the terminology of O. Goldreich. If your "DistP" is his "tcpP" (i.e. the analogical definition with distributions for which the probability of being in a given lexicographic interval is computable in polynomial time) then the question still makes sense for it. I'm not sure about AvgP and HeurP with which I'm not familiar. You can find the definition of sampP in the cstheory.stackexchange link where I spell it out – Squark Dec 28 '12 at 19:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.