<p>It is very likely that you can accomplish this in a generic setting. Almost certainly such a result <strong>has</strong> been proved in a generic setting already, but the references escape me at the moment. So here's an argument from scratch.</p>

<p>The writeup at <a href="http://oldblog.computationalcomplexity.org/media/ladner.pdf">http://oldblog.computationalcomplexity.org/media/ladner.pdf</a> has two proofs of Ladner's theorem. The second proof, by Russell Impagliazzo, produces a language $L_1$ of the form {$ x01^{f(|x|)}$} where $x$ encodes a satisfiable formula and $f$ is a particular polynomial time computable function. That is, by simply padding SAT with the appropriate number of $1$'s, you can get "NP-intermediate" sets. The padding is performed to "diagonalize" over all possible polynomial time reductions, so that no polynomial time reduction from SAT to $L_1$ will work (assuming $P \neq NP$). To prove that there are infinitely many degrees of hardness, one should be able to substitute $L_1$ in place of SAT in the above argument, and repeat the argument for $L_2 = ${$x 0 1^{f(|x|)} | x \in L_1$}. Repeat with $L_i  = ${$x 0 1^{f(|x|)} | x \in L_{i-1}$}.</p>

<p>It seems clear that such a proof can be generalized to classes $C$ and $D$, where (1) $C$ is properly contained in $D$, (2) $D$ has a complete language under $C$-reductions, (3) the list of all $C$-reductions can be recursively enumerated, and (4) the function $f$ is computable in $C$. Perhaps the only worrisome requirement is the last one, but if you look at the definition of $f$ in the link, it looks very easy to compute, for most reasonable classes $C$ that I can think of.</p>

CC BY-SA 2.5
2010-08-31T23:26:58.997Z
2010-08-31T23:26:58.997Z
Ryan Williams
<p>I think the answer is positive for <span class="math-container">$C=L$</span> and the uniform version of <span class="math-container">$NC$</span>. Ladner's proof does not use much other than what you stated and the fact that the smaller class is recursively represented and should work with minor modifications but I have not checked the details, take a look at Lance's writeup <a href="http://blog.computationalcomplexity.org/2003/03/foundations-of-complexity-lesson-16.html" rel="noreferrer">here</a>.</p>
<hr />
<h2>Update</h2>
<p>Check Ladner's paper <a href="http://dx.doi.org/10.1145%2F321864.321877" rel="noreferrer">On the Structure of Polynomial Time Reducibility</a></p>
<p>Here is the abstract:
Two notions of polynomial time reducibility, denoted here by <span class="math-container">$\leq_T^P$</span> and <span class="math-container">$\leq_m^P$</span>, were defined by Cook and Karp, respectively. The abstract property of these two relations on the domain of computable sets are investigated. Both relations prove to be dense and to have minimal pairs. Further, there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Our method of showing density yields the result that if <span class="math-container">$P \neq NP$</span> then there are members of <span class="math-container">$NP - P$</span> that are not polynomial complete.</p>
<p>THEOREM 1. If B is computable and not in <span class="math-container">$P$</span> then there exists a computable <span class="math-container">$A$</span> such that
<span class="math-container">$A \not \in P$</span>, <span class="math-container">$A \leq_m^P B$</span>,and <span class="math-container">$B \not \leq_T^P A$</span>.</p>
<p>Also see section 6 which discusses generalizations:</p>
<p>THEOREM 5. If <span class="math-container">$C$</span> is a <em>time class</em> then <span class="math-container">$\leq_m^C$</span> and <span class="math-container">$\leq_T^C$</span> are reflexive and transitive relations and Theorems 1-4 hold with <span class="math-container">$P$</span> replaced by <span class="math-container">$C$</span>.</p>
<p>THEOREM 7. If <span class="math-container">$C$</span> is a <em>space class</em> then <span class="math-container">$\leq_m^C$</span> and <span class="math-container">$\leq_T^C$</span> are reflexive and transitive relations and Theorems 1-4 hold with <span class="math-container">$P$</span> replaced by <span class="math-container">$C$</span>.</p>
<p>The terms <em>time class</em> and <em>space class</em> are defined in the paper.</p>

CC BY-SA 2.5
2010-08-31T18:17:31.100Z
The way I understood the Ladner and Impagliazzo proofs, they seemed to use some ingredients specific to NP, SAT, and many-one polynomial-time reductions.  My question is meant to be precisely about whether those ingredients can be used more generally.
András Salamon
CC BY-SA 2.5
2010-09-01T05:33:42.567Z
@András Salamon: No, actually Ladner's original proof does not use any fact about SAT other that it is computable (see theorem 1 above). In the section 6 he discusses the properties required for a reduction to work for his theorems. I think $L$ is a space class.
Kaveh
CC BY-SA 2.5
2010-09-01T05:35:05.967Z
I think that theorem can also be generalized to uniform circuit classes so theorem 1 would also work for $C=NC$ (haven't checked the details, I will add it to the post when I do or find a reference), but I don't think it can be generalized to nonuniform versions as the proof uses the fact that the complexity class is recursively represented. It would be interesting to know if theorem 1 also holds for the $C=AC^0$ (uniform version) which would answer Michaël Cadilhac's comment under the post.
Kaveh
CC BY-SA 2.5
2010-08-31T15:08:28.193Z
2010-08-31T19:08:43.553Z
2020-06-17T09:38:08.363Z
Kaveh
<p>I asked a similar question to Peter Shor at Mathoverflow <a href="https://mathoverflow.net/questions/34469/complete-problems-for-randomized-complexity-classes/34472#34472">here</a>. According to him, he is not aware of such a result. </p>

<p>Also, Ryan Williams said something funny about Ladner's theorem but I cannot find the link. It goes something like this: "The proof of Ladner's theorem is a zombie-like procedure where you take the head and torso of a NP-complete problem, and then stitch the arms and legs of a polynomial time algorithm".  It is rather unnatural way to define an NP-intermediate language, assuming $NP\neq P$.</p>

<p>I also thought about it, and maybe you can use Ryan's zombie-like procedure like this: Let $A$ be a complete set for $\sum_i^p$, and let $B \in \sum_{i-1}^p$. Then you can use the two approaches to the proof on $B$ by blowing holes or padding.</p>

<p>Another interesting problem is to consider a generalization of Ladner's to the promise versions of semantic classes, like promiseBPP, promiseMA, etc.</p>

CC BY-SA 2.5
2010-08-31T23:03:30.897Z
I forgot to mention that this is only with respect to PH of course, and it seems to be a more plausible approach than by taking just any complexity class.
Marcos Villagra
CC BY-SA 2.5
2010-08-31T23:04:27.570Z
Link: http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9253#9253
Ryan Williams
CC BY-SA 2.5
2010-09-01T05:41:15.547Z
I think the key point here is that the theorem 1 in Ladner's paper needs $C$ to be recursively represented as it is a diagonalization proof. The $BPP$ and $MA$ are semantic classes and AFAIK we don't know if they are recursively represented. On the other hand, uniform $NC$ is a syntactic class and is recursively represented.
Kaveh
CC BY-SA 2.5
2010-09-01T06:16:09.097Z
yes, the enumeration of machines from semantic classes is not recursive. But the promise versions of semantics classes (promiseBPP, promiseMA,...) are indeed sintactic.
Marcos Villagra
CC BY-SA 2.5
2010-08-31T22:52:03.890Z
2010-08-31T22:52:03.890Z
2017-04-13T12:57:54.530Z
Marcos Villagra
<p>The answer to your question is "yes" for a wide variety of classes and reductions, including logspace reductions and the classes you mentioned, as is proved in these papers:</p>

<blockquote>
  <p>H. Vollmer.  <a href="http://www.thi.uni-hannover.de/fileadmin/forschung/publikationen/daten/vollmer90.ps.gz">The gap-language technique revisited</a>.  Computer Science Logic, Lecture Notes in Computer Science Vol. 533, pages 389-399, 1990.</p>
  
  <p>K. Regan and H. Vollmer.  <a href="http://www.thi.uni-hannover.de/fileadmin/forschung/publikationen/daten/reg-vol95.ps.gz">Gap-languages and log-time complexity classes</a>.  Theoretical Computer Science, 188(1-2):101-116, 1997.</p>
</blockquote>

<p>(You can download gzipped postscript files of these papers <a href="http://www.thi.uni-hannover.de/en/research/publications/">here</a>.)</p>

<p>The proofs follow the basic principle of Uwe Schöning's extension of Ladner's theorem:</p>

<blockquote>
  <p>Uwe Schöning.  <a href="http://www.sciencedirect.com/science/article/pii/0304397582901141">A uniform approach to obtain diagonal sets in complexity classes</a>.  Theoretical Computer Science 18(1):95-103, 1982.</p>
</blockquote>

<p>Schöning's proof has always been my favorite proof of Ladner's theorem -- it's both simple and general.</p>

CC BY-SA 2.5
2010-09-02T02:37:00.733Z
and what about promise classes?
Marcos Villagra
CC BY-SA 3.0
2010-09-02T02:33:12.170Z
2011-08-07T21:30:28.297Z
2011-08-07T21:30:28.297Z
John Watrous
<p><a href="http://doi.acm.org/10.1145/321864.321877">Ladner's Theorem</a> states that if P ≠ NP, then there is an infinite hierarchy of <a href="http://en.wikipedia.org/wiki/Complexity_class">complexity classes</a> strictly containing P and strictly contained in NP.  The proof uses the completeness of SAT under many-one reductions in NP.  The hierarchy contains complexity classes constructed by a kind of diagonalization, each containing some language to which the languages in the lower classes are not many-one reducible.</p>

<p>This motivates my question:</p>

<blockquote>
  <p>Let C be a complexity class, and let D be a complexity class that strictly contains C.  If D contains languages that are complete for some notion of reduction, does there exist an infinite hierarchy of complexity classes between C and D, with respect to the reduction?</p>
</blockquote>

<p>More specifically, I would like to know if there are results known for D = P and C = <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aL#logcfl">LOGCFL</a> or C = <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aN#nc">NC</a>, for an appropriate notion of reduction.</p>

<hr>

<p>Ladner's paper already includes Theorem 7 for space-bounded classes C, as Kaveh pointed out in an answer.  In its strongest form this says: if NL ≠ NP then there is an infinite sequence of languages between NL and NP, of strictly increasing hardness.  This is slightly more general than the usual version (Theorem 1), which is conditional on P ≠ NP.  However, Ladner's paper only considers D = NP.</p>

CC BY-SA 2.5
2010-08-31T15:12:53.297Z
One may first ask the question focusing on classes we already  know differ.  For instance, is there an infinite hierarchy between AC$^0$ and AC$^0$[6], with respect to projections ?  That looks like a tough question! :-)
Michaël Cadilhac
CC BY-SA 2.5
2010-08-31T18:14:40.513Z
See also http://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np for a question about the interval from P to NP.
András Salamon
<cc.complexity-theory><reference-request><np-intermediate>
Generalized Ladner's Theorem
András Salamon
# Generalized Ladner's Theorem

(Asked by: username_0 on 2010-08-31)

[Ladner's Theorem](http://doi.acm.org/10.1145/321864.321877) states that if P ≠ NP, then there is an infinite hierarchy of [complexity classes](http://en.wikipedia.org/wiki/Complexity_class) strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-one reductions in NP. The hierarchy contains complexity classes constructed by a kind of diagonalization, each containing some language to which the languages in the lower classes are not many-one reducible.

This motivates my question:

> Let C be a complexity class, and let D be a complexity class that strictly contains C. If D contains languages that are complete for some notion of reduction, does there exist an infinite hierarchy of complexity classes between C and D, with respect to the reduction?

More specifically, I would like to know if there are results known for D = P and C = [LOGCFL](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aL#logcfl) or C = [NC](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aN#nc), for an appropriate notion of reduction.

---

Ladner's paper already includes Theorem 7 for space-bounded classes C, as Kaveh pointed out in an answer. In its strongest form this says: if NL ≠ NP then there is an infinite sequence of languages between NL and NP, of strictly increasing hardness. This is slightly more general than the usual version (Theorem 1), which is conditional on P ≠ NP. However, Ladner's paper only considers D = NP.

**Tags:** cc.complexity-theory, reference-request, np-intermediate
> **Comments:**
> **username_1**: One may first ask the question focusing on classes we already  know differ.  For instance, is there an infinite hierarchy between AC$^0$ and AC$^0$[6], with respect to projections ?  That looks like a tough question! :-)  
> **username_0**: See also http://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np for a question about the interval from P to NP.  

---

## 4 answers

### Answer by username_5 on 2010-09-02. Score: 38 | Accepted answer

The answer to your question is "yes" for a wide variety of classes and reductions, including logspace reductions and the classes you mentioned, as is proved in these papers:

> H. Vollmer. [The gap-language technique revisited](http://www.thi.uni-hannover.de/fileadmin/forschung/publikationen/daten/vollmer90.ps.gz). Computer Science Logic, Lecture Notes in Computer Science Vol. 533, pages 389-399, 1990.
>
> K. Regan and H. Vollmer. [Gap-languages and log-time complexity classes](http://www.thi.uni-hannover.de/fileadmin/forschung/publikationen/daten/reg-vol95.ps.gz). Theoretical Computer Science, 188(1-2):101-116, 1997.

(You can download gzipped postscript files of these papers [here](http://www.thi.uni-hannover.de/en/research/publications/).)

The proofs follow the basic principle of Uwe Schöning's extension of Ladner's theorem:

> Uwe Schöning. [A uniform approach to obtain diagonal sets in complexity classes](http://www.sciencedirect.com/science/article/pii/0304397582901141). Theoretical Computer Science 18(1):95-103, 1982.

Schöning's proof has always been my favorite proof of Ladner's theorem -- it's both simple and general.

> **Comments:**
> **username_4**: and what about promise classes?  

---

### Answer by username_2 on 2010-08-31. Score: 15

It is very likely that you can accomplish this in a generic setting. Almost certainly such a result **has** been proved in a generic setting already, but the references escape me at the moment. So here's an argument from scratch.

The writeup at <http://oldblog.computationalcomplexity.org/media/ladner.pdf> has two proofs of Ladner's theorem. The second proof, by Russell Impagliazzo, produces a language $L\_1$ of the form {$ x01^{f(|x|)}$} where $x$ encodes a satisfiable formula and $f$ is a particular polynomial time computable function. That is, by simply padding SAT with the appropriate number of $1$'s, you can get "NP-intermediate" sets. The padding is performed to "diagonalize" over all possible polynomial time reductions, so that no polynomial time reduction from SAT to $L\_1$ will work (assuming $P \neq NP$). To prove that there are infinitely many degrees of hardness, one should be able to substitute $L\_1$ in place of SAT in the above argument, and repeat the argument for $L\_2 = ${$x 0 1^{f(|x|)} | x \in L\_1$}. Repeat with $L\_i = ${$x 0 1^{f(|x|)} | x \in L\_{i-1}$}.

It seems clear that such a proof can be generalized to classes $C$ and $D$, where (1) $C$ is properly contained in $D$, (2) $D$ has a complete language under $C$-reductions, (3) the list of all $C$-reductions can be recursively enumerated, and (4) the function $f$ is computable in $C$. Perhaps the only worrisome requirement is the last one, but if you look at the definition of $f$ in the link, it looks very easy to compute, for most reasonable classes $C$ that I can think of.


---

### Answer by username_3 on 2010-08-31. Score: 9

I think the answer is positive for $C=L$ and the uniform version of $NC$. Ladner's proof does not use much other than what you stated and the fact that the smaller class is recursively represented and should work with minor modifications but I have not checked the details, take a look at Lance's writeup [here](http://blog.computationalcomplexity.org/2003/03/foundations-of-complexity-lesson-16.html).

---

## Update

Check Ladner's paper [On the Structure of Polynomial Time Reducibility](http://dx.doi.org/10.1145%2F321864.321877)

Here is the abstract:
Two notions of polynomial time reducibility, denoted here by $\leq\_T^P$ and $\leq\_m^P$, were defined by Cook and Karp, respectively. The abstract property of these two relations on the domain of computable sets are investigated. Both relations prove to be dense and to have minimal pairs. Further, there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Our method of showing density yields the result that if $P \neq NP$ then there are members of $NP - P$ that are not polynomial complete.

THEOREM 1. If B is computable and not in $P$ then there exists a computable $A$ such that
$A \not \in P$, $A \leq\_m^P B$,and $B \not \leq\_T^P A$.

Also see section 6 which discusses generalizations:

THEOREM 5. If $C$ is a *time class* then $\leq\_m^C$ and $\leq\_T^C$ are reflexive and transitive relations and Theorems 1-4 hold with $P$ replaced by $C$.

THEOREM 7. If $C$ is a *space class* then $\leq\_m^C$ and $\leq\_T^C$ are reflexive and transitive relations and Theorems 1-4 hold with $P$ replaced by $C$.

The terms *time class* and *space class* are defined in the paper.

> **Comments:**
> **username_0**: The way I understood the Ladner and Impagliazzo proofs, they seemed to use some ingredients specific to NP, SAT, and many-one polynomial-time reductions.  My question is meant to be precisely about whether those ingredients can be used more generally.  
> **username_3**: @András Salamon: No, actually Ladner's original proof does not use any fact about SAT other that it is computable (see theorem 1 above). In the section 6 he discusses the properties required for a reduction to work for his theorems. I think $L$ is a space class.  
> **username_3**: I think that theorem can also be generalized to uniform circuit classes so theorem 1 would also work for $C=NC$ (haven't checked the details, I will add it to the post when I do or find a reference), but I don't think it can be generalized to nonuniform versions as the proof uses the fact that the complexity class is recursively represented. It would be interesting to know if theorem 1 also holds for the $C=AC^0$ (uniform version) which would answer Michaël Cadilhac's comment under the post.  

---

### Answer by username_4 on 2010-08-31. Score: 6

I asked a similar question to Peter Shor at Mathoverflow [here](https://mathoverflow.net/questions/34469/complete-problems-for-randomized-complexity-classes/34472#34472). According to him, he is not aware of such a result.

Also, Ryan Williams said something funny about Ladner's theorem but I cannot find the link. It goes something like this: "The proof of Ladner's theorem is a zombie-like procedure where you take the head and torso of a NP-complete problem, and then stitch the arms and legs of a polynomial time algorithm". It is rather unnatural way to define an NP-intermediate language, assuming $NP\neq P$.

I also thought about it, and maybe you can use Ryan's zombie-like procedure like this: Let $A$ be a complete set for $\sum\_i^p$, and let $B \in \sum\_{i-1}^p$. Then you can use the two approaches to the proof on $B$ by blowing holes or padding.

Another interesting problem is to consider a generalization of Ladner's to the promise versions of semantic classes, like promiseBPP, promiseMA, etc.

> **Comments:**
> **username_4**: I forgot to mention that this is only with respect to PH of course, and it seems to be a more plausible approach than by taking just any complexity class.  
> **username_2**: Link: http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9253#9253  
> **username_3**: I think the key point here is that the theorem 1 in Ladner's paper needs $C$ to be recursively represented as it is a diagonalization proof. The $BPP$ and $MA$ are semantic classes and AFAIK we don't know if they are recursively represented. On the other hand, uniform $NC$ is a syntactic class and is recursively represented.  
> **username_4**: yes, the enumeration of machines from semantic classes is not recursive. But the promise versions of semantics classes (promiseBPP, promiseMA,...) are indeed sintactic.  

---

