44
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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! :-) $\endgroup$ – Michaël Cadilhac Aug 31 '10 at 15:12
  • $\begingroup$ See also cstheory.stackexchange.com/questions/52/… for a question about the interval from P to NP. $\endgroup$ – András Salamon Aug 31 '10 at 18:14
32
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ and what about promise classes? $\endgroup$ – Marcos Villagra Sep 2 '10 at 2:37
12
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Aug 31 '10 at 18:17
  • $\begingroup$ @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. $\endgroup$ – Kaveh Sep 1 '10 at 5:33
  • $\begingroup$ 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. $\endgroup$ – Kaveh Sep 1 '10 at 5:35
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marcos Villagra Aug 31 '10 at 23:03
  • 5
    $\begingroup$ Link: mathoverflow.net/questions/9221/… $\endgroup$ – Ryan Williams Aug 31 '10 at 23:04
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 1 '10 at 5:41
  • $\begingroup$ yes, the enumeration of machines from semantic classes is not recursive. But the promise versions of semantics classes (promiseBPP, promiseMA,...) are indeed sintactic. $\endgroup$ – Marcos Villagra Sep 1 '10 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.