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.
- Are there "NP-Intermediate-Complete" problems - that is, NP-Intermediate problems to which every other NP-Intermediate problem is polytime reducible?
- 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?
- 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.