Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I approximately copied the brief "introduction" to average-case complexity theory of NP from my previous question. However, this question is completely different, so please read on

It is conjectured that $\mathsf{NP}$-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability distribution $X_n$ on $\lbrace 0,1 \rbrace^n$, $(S, X)$ is called "hard in the typical case" when for any algorithm $A$ and polynomial $q(n)$, the probability $P_n$ that $A$ decides membership in $S$ correctly in time at most $q(n)$ for an $X_n$-random element of $\lbrace 0,1 \rbrace^n$ is s.t. $1-P_n$ decreases with $n$ slower than some polynomial

We henceforth restrict attention to $X_n$ that are polynomial-time-sampleable, that is, $X_n$ can be sampled by a random algorithm with time complexity polynomial in $n$. We define a "distributional (decision) problem" to be a pair $(S, X)$ with $S$ a language and $X$ polynomial-time-sampleable. The class of distributional problems which are feasible (not hard) in the typical case will be denoted $\mathsf{sampP}$. The class of distributional problems $(S, X)$ s.t. $S \in \mathsf{NP}$ will be denoted $\mathsf{sampNP}$.

It can be shown than there are distributional problems $(S, X) \in \mathsf{sampNP}$ such that for any $(T, Y) \in \mathsf{sampNP}$, $(T, Y)$ can be reduced to $(S, X)$ in an appropriate sense, in particular if $(S, X) \in \mathsf{sampP}$ then $(T, Y) \in \mathsf{sampP}$ i.e. in such case $\mathsf{sampNP} \subset \mathsf{sampP}$ (note that $\mathsf{sampNP} \ne \mathsf{sampP}$ since $\mathsf{sampP}$ is uncountable: the language can be "tweaked" arbitrarily in an infinite set of words which is "rare" w.r.t. the distribition)

O. Goldreich calls such problems $\mathsf{sampNP}$-complete. For most (all?) natural $\mathsf{NP}$-complete languages $S$, we can find $X$ s.t. $(S, X)$ is $\mathsf{sampNP}$-complete. It is conjectured that $\mathsf{sampNP} \not\subseteq \mathsf{sampP}$. In particular, it is a necessary condition for existence of one-way functions

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 average-case theory?

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?

A theorem by Schöning allows generalization of Ladner's theorem to many cases, e.g. see John Watrous' answer to a previous question of mine to see how Schöning's theorem allows proving that if $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ then $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$. 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 Schöning's theorem.

The second reason is that the result crucially depends on the fact that $\mathsf{NP} \cap \mathsf{P/poly}$ 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 Schöning's reasoning for this case. So, maybe there are no $\mathsf{NP}$-intermediate problems in the average-case sense?

EDIT: Impagliazzo'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 it is trivially in $\mathsf{sampP}$. At least this is so for natural $\mathsf{sampNP}$-complete problems since their distributions are close to uniform

EDIT: I changed the title from "Are problems in $\mathsf{NPI}$ average-case polynomial?" to "Are there $\mathsf{sampNP}$-intermediate problems?" since the former formulation seems inaccurate. AFAIK it is possible there are problems in $\mathsf{NPI}$ which are $\mathsf{sampNP}$-complete since $\mathsf{sampP}$-reductions are not $\mathsf{P}$-reductions. This is not so for $\mathsf{tpcP}$ for which the question also makes sense

share|cite|improve this question
This would be possible if there was a recursive enumeration of unbounded functions $f_i:N \to N$ s.t. for any computable unbounded function $g:N \to 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. - I am not sure, but I think this may be a mistake. An enumeration of all TMs $f_i$ should suffice, right? I think the diagonalization argument requires enumeration in decreasing order; but that mightn't be needed: maybe we can "recursively present" sampNP $\cap$ sampP by dovetailing among the TMs $f_i$....? – usul Jan 9 '13 at 15:10
@usul : The diagonalization argument doesn't require decreasing order since you just take the mimimum of functions 1 to i at place i. An enumeration of all computable functions is impossible as seen by a simpler diagonalization argument: just take $g(i) := f_i(i) + 1$ – Squark Jan 12 '13 at 15:33
OK, I see the argument for (total) computable functions. But my thought was that the functions might not need to be total. Can we dovetail among all Turing Machines (something like: for $i=1,\dots$ run TMs $1$ to $i$ for $i$ steps each on inputs $1$ to $i$)? – usul Jan 12 '13 at 17:28
@usul : I don't understand how you use this to recursively present sampNP ∩ sampP – Squark Jan 12 '13 at 17:45

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.