<p><em>I approximately copied the brief "introduction" to average-case complexity theory of NP from <a href="https://cstheory.stackexchange.com/questions/14797">my previous question</a>. However, this question is completely different, so please read on</em></p>

<p>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</p>

<p>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}$.</p>

<p>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)</p>

<p>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</p>

<p>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?</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>A theorem by Schöning allows generalization of Ladner's theorem to many cases, e.g. see John Watrous' answer to <a href="https://cstheory.stackexchange.com/questions/14670">a previous question of mine</a> 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  </p>

<p>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.</p>

<p>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 <em>some</em> $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</p>

<p>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?</p>

<p>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</p>

<p>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</p>

CC BY-SA 3.0
2013-01-09T15:10:31.567Z
*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
CC BY-SA 3.0
2013-01-12T15:33:06.140Z
@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$
Vanessa
CC BY-SA 3.0
2013-01-12T17:28:49.563Z
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
CC BY-SA 3.0
2013-01-12T17:45:41.287Z
@usul : I don't understand how you use this to recursively present sampNP ∩ sampP
Vanessa
<cc.complexity-theory><p-vs-np><average-case-complexity><np-intermediate>
Are there sampNP-intermediate problems?
Vanessa
# Are there sampNP-intermediate problems?

(Asked by: username_0 on 2012-12-22)

*I approximately copied the brief "introduction" to average-case complexity theory of NP from [my previous question](https://cstheory.stackexchange.com/questions/14797). 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](https://cstheory.stackexchange.com/questions/14670) 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

**Tags:** cc.complexity-theory, p-vs-np, average-case-complexity, np-intermediate
> **Comments:**
> **username_1**: *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$....?  
> **username_0**: @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$  
> **username_1**: 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$)?  
> **username_0**: @usul : I don't understand how you use this to recursively present sampNP ∩ sampP  

---

## 0 answers

