15
$\begingroup$

Assume P $\ne$ NP.

Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete). I have found some veiled references online that suggest (I think) that there are many "levels" of mutually reducible languages within NPI that definitely do not all collapse into one.

I have some questions about the structure of these levels.

  1. Are there "NP-Intermediate-Complete" problems - that is, NP-Intermediate problems to which every other NP-Intermediate problem is polytime reducible?
  2. Sort NP - P into equivalence classes, where mutual reducibility is the equivalence relation. Now impose an ordering on these equivalence classes: $A > B$ if the problems in $B$ reduce to problems in $A$ (so clearly the NP-Complete equivalence class is the maximum element). Is this a total ordering (i.e. the problems are arranged in an infinite descending chain)? If not, does the "tree structure" of the partial ordering have a finite branching factor?
  3. Are there any other interesting known structural components of NP - P? Are there any interesting open questions about the underlying structure?

If any of these are currently unknown, I would be interested to hear that as well.

Thanks!

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ A weak version of this is that there are "Graph-Isomorphism-Complete" problems. $\endgroup$
    – Suresh Venkat
    Jan 28, 2014 at 8:07
  • 7
    $\begingroup$ The answer to 1. is "yes and no" I think: Yes because as Suresh says, you can have GI-complete problems (and $\pi$-complete problems for other problems $\pi$). And no because by Ladner's proof, there is an infinite hierarchy of $\mathsf{NP}$-intermediate classes and if I am not mistaken, having a $\mathsf{NP}$-intermediate-complete problem would collapse this hierarchy (and thus by contradiction prove $\mathsf P=\mathsf{NP}$), in the same way as the polynomial hierarchy cannot have a complete problem if it does not collapse. $\endgroup$
    – Bruno
    Jan 28, 2014 at 8:31
  • $\begingroup$ Thanks, Bruno - can this info all be found in Ladner's original paper, or should are there other relevant sources? $\endgroup$
    – GMB
    Jan 28, 2014 at 8:40
  • $\begingroup$ You can also take a look to the Downey and Fortnow paper: Uniformly Hard Languages; in which the Ladner's theorem proof given in Appendix A.1 shows that the polynomial time degrees of computable languages are a dense partial ordering. They also conjecture that if there exist uniformly hard sets in NP then there exist incomplete uniformly hard sets. $\endgroup$
    – Marzio De Biasi
    Jan 28, 2014 at 9:05
  • 1
    $\begingroup$ for another reference for 1. and a possibly useful resource, see Ryan's answer, and Schoening's paper cited in it. $\endgroup$
    – Sasho Nikolov
    Jan 28, 2014 at 12:52

1 Answer 1

Reset to default
34
$\begingroup$

I don't really have references for these results--they aren't hard to prove once you understand Ladner's theorem.

  1. No, for any NP-incomplete set A there is another set B strictly between A and SAT.

  2. These equivalence classes are known as polynomial-many-one degrees. You can embed any finite poset into the degrees below NP. In particular the degrees are not totally ordered or finitely branching.

  3. This all depends on what you mean by "interesting". There is a huge theory of the degree structure of the computable sets (see Soare's book for instance) and many of those questions have not been ported down to polynomial-time sets. For instance, can you have NP sets A and B whose join is equivalent to SAT and whose meet is equivalent to the empty set?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by meet, some kind of intersection? I suppose the join of $A$ and $B$ is $C$ such that $(x,y) \in C$ iff $x \in A$ and $y \in B$, is that right? $\endgroup$
    – John D.
    Jan 28, 2014 at 13:50
  • 8
    $\begingroup$ These are terms of lattice theory: the join of a subset is its least upper bound (if it exists) and the meet the greatest lower bound. $\endgroup$
    – Bruno
    Jan 28, 2014 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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