# 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?

• – Ariel Apr 12 '17 at 19:37
• Your title and question are asking very different questions. – Raphael Nov 4 '18 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. – PPenguin Nov 5 '18 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 '18 at 22:03

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.
• @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? – Noah Schweber Nov 3 '18 at 17:59