# Are there “NP-Intermediate-Complete” problems?

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!

• A weak version of this is that there are "Graph-Isomorphism-Complete" problems. – Suresh Venkat Jan 28 '14 at 8:07
• 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. – Bruno Jan 28 '14 at 8:31
• Thanks, Bruno - can this info all be found in Ladner's original paper, or should are there other relevant sources? – GMB Jan 28 '14 at 8:40
• 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. – Marzio De Biasi Jan 28 '14 at 9:05
• for another reference for 1. and a possibly useful resource, see Ryan's answer, and Schoening's paper cited in it. – Sasho Nikolov Jan 28 '14 at 12:52

• 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? – John D. Jan 28 '14 at 13:50