# Are there any decision complexity classes which have no "complete" subclass?

Are there any decision complexity classes, where the "-Hard" version of the class does not intersect with the original class?

• Apr 12, 2017 at 19:37
• Your title and question are asking very different questions.
– Raphael
Nov 4, 2018 at 18:38
• @Raphael How are they "very" different? For a decision class X, X-Hard is the class of decision problems such that every problem in X can be reduced to this problem (via a reduction appropriate for X). If X-Hard intersects with X, the class of decision problems in the intersection is X-complete. Nov 5, 2018 at 2:56
• You are correct, the two questions are the same. However, mostly uninteresting: just pick a suitable notion of reduction, and there you go. For the purposes of discussion, you need to either fix a certain form of reduction, or you have to specify whether you're interesting in a complexity class which has this propery for some or all notions of reduction.
– Raphael
Nov 14, 2018 at 22:03

Apart from the many answers from the Mathoverflow link commented above by Ariel, we have a very simple example as follows.

Under widely accepted conjecture that $\mathrm{P}\neq \mathrm{NP}$, we have that $\mathrm{NP}\setminus \mathrm{NP}$-$\mathrm{complete}$ does not have complete problem and therefore the "hard" part of it is well "above" it.

For the proof, use Ladner's result on $\mathrm{p}$-degree, for any two different $\mathrm{p}$-degrees $\mathrm{A}$ and $\mathrm{B}$, if $\mathrm{A}<_p\mathrm{B}$, then there must exist another $\mathrm{p}$-degree $\mathrm{C}$ in between: $\mathrm{A}<_p\mathrm{C}<_p\mathrm{B}$. So by removing $\mathrm{NP}$-$\mathrm{complete}$ from $\mathrm{NP}$, every $\mathrm{p}$-degree below the complete degree always has another non-complete degree above it.

• This doesn't answer the question: it asks about complete, you answer for "hard".
– Raphael
Nov 3, 2018 at 7:08
• @Raphael "Every $p$-degree [of a problem in NP] below the complete degree has another [NP,] non-[NP-]complete degree above it" I think this does answer the question, unless I'm missing something? Nov 3, 2018 at 17:59
• @NoahSchweber Ah, I checked the title but the question body contained a different question. Never mind.
– Raphael
Nov 4, 2018 at 18:38