5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Does this question still make sense for other "average case" complexity classes like AvgP, DistP, and HeurP? I'm getting these from complexityzoo.uwaterloo.ca/Complexity_Zoo, which incidentally doesn't list sampP. $\endgroup$ Dec 28, 2012 at 18:49
  • $\begingroup$ @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 $\endgroup$
    – Vanessa
    Dec 28, 2012 at 19:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.