4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ related mathoverflow.net/questions/27572/… $\endgroup$ – Ariel Apr 12 '17 at 19:37
  • 1
    $\begingroup$ Your title and question are asking very different questions. $\endgroup$ – Raphael Nov 4 '18 at 18:38
  • $\begingroup$ @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. $\endgroup$ – PPenguin Nov 5 '18 at 2:56
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 14 '18 at 22:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This doesn't answer the question: it asks about complete, you answer for "hard". $\endgroup$ – Raphael Nov 3 '18 at 7:08
  • $\begingroup$ @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? $\endgroup$ – Noah Schweber Nov 3 '18 at 17:59
  • $\begingroup$ @NoahSchweber Ah, I checked the title but the question body contained a different question. Never mind. $\endgroup$ – Raphael Nov 4 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.