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

<ol>
<li><p>No, for any NP-incomplete set A there is another set B strictly between A and SAT.</p></li>
<li><p>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. </p></li>
<li><p>This all depends on what you mean by "interesting". There is a huge theory of the degree structure of the computable sets (see <a href="http://rads.stackoverflow.com/amzn/click/0387152997">Soare's book</a> 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? </p></li>
</ol>

CC BY-SA 3.0
2014-01-28T13:50:28.120Z
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.
CC BY-SA 3.0
2014-01-28T16:12:37.260Z
These are terms of [lattice theory](https://en.wikipedia.org/wiki/Lattice_%28order%29): the **join** of a subset is its least upper bound (if it exists) and the **meet** the greatest lower bound.
Bruno
CC BY-SA 4.0
2024-10-23T18:57:55.253Z
@JohnD. Bruno's comment does not actually define meet and join in the present context. Here one is talking about equivalence classes of NP sets up to polytime-many-one reductions ordered by reduction, the join $A\vee B$ is the least degree greater than $A$ and $B$ if it exists, similarly for the meet $A\wedge B$. On this set one can a priori only partially define the meet and join binary operations. Turing degrees for instance do not form a lattice: for any 2 degrees the join always exists, but the meet need not exist. Lance's question requires both meet and join to exist for $A$ and $B$.
plm
CC BY-SA 3.0
2014-01-28T13:29:40.077Z
2014-01-28T13:29:40.077Z
Lance Fortnow
<p>Assume P $\ne$ NP.</p>

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

<p>I have some questions about the structure of these levels.</p>

<ol>
<li>Are there "NP-Intermediate-Complete" problems - that is, NP-Intermediate problems to which every other NP-Intermediate problem is polytime reducible?</li>
<li>Sort NP - P into equivalence classes, where mutual reducibility is the equivalence relation.  Now impose an ordering on these equivalence classes: $A &gt; 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?</li>
<li>Are there any other interesting known structural components of NP - P?  Are there any interesting open questions about the underlying structure?</li>
</ol>

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

<p>Thanks!</p>

CC BY-SA 3.0
2014-01-28T08:07:10.730Z
A weak version of this is that there are "Graph-Isomorphism-Complete" problems.
Suresh Venkat
CC BY-SA 3.0
2014-01-28T08:31:32.607Z
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
CC BY-SA 3.0
2014-01-28T08:40:19.217Z
Thanks, Bruno - can this info all be found in Ladner's original paper, or should are there other relevant sources?
GMB
CC BY-SA 3.0
2014-01-28T09:05:20.187Z
You can also take a look to the Downey and Fortnow paper: [Uniformly Hard Languages](http://people.cs.uchicago.edu/~fortnow/papers/uniform.pdf); 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
CC BY-SA 3.0
2014-01-28T09:21:49.287Z
I've never read Ladner original paper actually. You can find this info as a comment in Goldreich's [Computational COmplexity](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html) book. I mean for the infinite hierarchy. For the non-existence of complete problems for the class $\mathsf{NP}$-intermediate, it is an easy consequence. The reference given by Marzio is very good too!
Bruno
CC BY-SA 3.0
2014-01-28T12:52:30.513Z
for another reference for 1. and a possibly useful resource, see [Ryan's answer](http://cstheory.stackexchange.com/a/8046/4896), and Schoening's paper cited in it.
Sasho Nikolov
CC BY-SA 3.0
2014-01-29T18:32:32.743Z
sees similar to MATs question [Intermediate NP-complete problems?](http://cstheory.stackexchange.com/questions/16692/intermediate-mathsfnp-complete-problems) but not sure exactly how they relate, it might help to compare/contrast them together
vzn
CC BY-SA 4.0
2020-02-18T05:17:37.373Z
@Bruno Can we at least prove that there are NP-intermediate-complete problems assuming $\mathsf{P=NP}$ (whether this assumption is correct or not is another matter).
Cyriac Antony
CC BY-SA 4.0
2020-02-24T12:49:43.347Z
@CyriacAntony If $\mathsf P = \mathsf{NP}$, there is no such notion of $\mathsf{NP}$-intermediate problems, since all problems that are in $\mathsf{NP}$ (including those in $\mathsf P$, the $\mathsf{NP}$-intermediate or the $\mathsf{NP}$-compete) belong to $\mathsf P$... So the question does not make sense to me.
Bruno
<cc.complexity-theory><np><np-intermediate>
Are there "NP-Intermediate-Complete" problems?
GMB
# Are there "NP-Intermediate-Complete" problems?

(Asked by: username_0 on 2014-01-28)

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!

**Tags:** cc.complexity-theory, np, np-intermediate

> **Comments:**
> **username_1**: A weak version of this is that there are "Graph-Isomorphism-Complete" problems.  
> **username_2**: 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.  
> **username_0**: Thanks, username_2 - can this info all be found in Ladner's original paper, or should are there other relevant sources?  
> **username_3**: You can also take a look to the Downey and Fortnow paper: [Uniformly Hard Languages](http://people.cs.uchicago.edu/~fortnow/papers/uniform.pdf); 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.  
> **username_2**: I've never read Ladner original paper actually. You can find this info as a comment in Goldreich's [Computational COmplexity](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html) book. I mean for the infinite hierarchy. For the non-existence of complete problems for the class $\mathsf{NP}$-intermediate, it is an easy consequence. The reference given by Marzio is very good too!  
> **username_4**: for another reference for 1. and a possibly useful resource, see [Ryan's answer](http://cstheory.stackexchange.com/a/8046/4896), and Schoening's paper cited in it.  
> **username_5**: sees similar to MATs question [Intermediate NP-complete problems?](http://cstheory.stackexchange.com/questions/16692/intermediate-mathsfnp-complete-problems) but not sure exactly how they relate, it might help to compare/contrast them together  
> **username_6**: @username_2 Can we at least prove that there are NP-intermediate-complete problems assuming $\mathsf{P=NP}$ (whether this assumption is correct or not is another matter).  
> **username_2**: @CyriacAntony If $\mathsf P = \mathsf{NP}$, there is no such notion of $\mathsf{NP}$-intermediate problems, since all problems that are in $\mathsf{NP}$ (including those in $\mathsf P$, the $\mathsf{NP}$-intermediate or the $\mathsf{NP}$-compete) belong to $\mathsf P$... So the question does not make sense to me.  

---

## 1 answers

### Answer by username_7 on 2014-01-28. Score: 35 | Accepted answer

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](http://rads.stackoverflow.com/amzn/click/0387152997) 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?

> **Comments:**
> **username_8**: 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?  
> **username_2**: These are terms of [lattice theory](https://en.wikipedia.org/wiki/Lattice_%28order%29): the **join** of a subset is its least upper bound (if it exists) and the **meet** the greatest lower bound.  
> **username_9**: @JohnD. username_2's comment does not actually define meet and join in the present context. Here one is talking about equivalence classes of NP sets up to polytime-many-one reductions ordered by reduction, the join $A\vee B$ is the least degree greater than $A$ and $B$ if it exists, similarly for the meet $A\wedge B$. On this set one can a priori only partially define the meet and join binary operations. Turing degrees for instance do not form a lattice: for any 2 degrees the join always exists, but the meet need not exist. Lance's question requires both meet and join to exist for $A$ and $B$.  

---

