Generalized Ladner's Theorem

Question

Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes 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 or C = 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.

Answer 1

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. 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. Theoretical Computer Science, 188(1-2):101-116, 1997.

(You can download gzipped postscript files of these papers here.)

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

Answer 2

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 3

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.

---

Update

Check Ladner's paper On the Structure of Polynomial Time Reducibility

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.

Answer 4

I asked a similar question to Peter Shor at Mathoverflow here. 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.