5
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ related mathoverflow.net/questions/27572/… $\endgroup$
    – Ariel
    Apr 12, 2017 at 19:37
  • 1
    $\begingroup$ Your title and question are asking very different questions. $\endgroup$
    – Raphael
    Nov 4, 2018 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, 2018 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, 2018 at 22:03

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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