8
$\begingroup$

Suppose $\Pi$ is a decidable decision problem.

Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?

Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?

$\endgroup$
  • $\begingroup$ No. You should probably refer to the explicit definition of NP-hardness. Hint: consider problems in coNP. $\endgroup$ – mdxn Dec 16 '14 at 7:05
  • $\begingroup$ @mdx - for all we know, problems in coNP might also reside in NP. $\endgroup$ – A A Dec 16 '14 at 7:27
  • 1
    $\begingroup$ @A A Of course. My hint was intended for you to consider the case where they are separated, which you have done. Your edit does improve the question and make it more interesting. $\endgroup$ – mdxn Dec 16 '14 at 7:38
5
$\begingroup$

If you assume that $\mathsf{NP}\neq\mathsf{coNP}$ then any coNP-complete problem gives a counterexample. I would guess that one can refute your conjecture unconditionally.

$\endgroup$
  • $\begingroup$ I agree, but I'm wondering if this can be shown false without any unknown assumptions. $\endgroup$ – A A Dec 16 '14 at 7:27
3
$\begingroup$

If $P=NP$ then

$\Pi \not\in NP$
$\implies$
$P=NP$ and $\Pi$ is neither the empty language nor the full language
$\implies$
$\Pi$ is $NP$-hard.

Let $\operatorname{int}(s)$ denote the result of putting a leading 1 on the most significant end of $s$ and then parsing the result as an integer in binary.

If $P\neq NP$ then for each subset $S$ of $\{0,1\}^*$ that is not in $\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$,
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$ is not in NP since $S$ is too hard, is decidable if and only if $S$ is, and is not NP-hard even with respect to Turing reductions since for any polynomial bound, there are only polynomially many possibilities for the subset of that language consisting of the elements that fit within the length bound, so one could try the search-to-decision reduction with each of them.

$\endgroup$
  • 2
    $\begingroup$ Edit history "Fixed bad spacing". No you did not. Can you please get it into your head that your spacing "fixed" only work on your own screen? For anybody else, who uses a different browser, different default fonts, or even the same browser, the same fonts but a slightly different window size finds your posts very hard to read because they're full of seemingly random spacing commands and line breaks. STOP DOING IT. JUST STOP. $\endgroup$ – David Richerby Jun 29 '15 at 6:01
  • 2
    $\begingroup$ Especially, please stop adding negative spaces, which cause characters to run into each other. $\endgroup$ – David Richerby Jun 29 '15 at 6:06
  • 2
    $\begingroup$ Please stop doing this. Such microedits look good (at most) on your browser and settings. As previously discussed, you might want to reconsider whether this site is for you if you are uncomfortable with other people editing your posts. $\endgroup$ – Juho Jun 29 '15 at 6:09
2
$\begingroup$

Completeness for a class means it is universal for the class, i.e. other problems in the class can be solved using it. If there is a difficult problem in a class then all universal problems for the class will also be difficult. But the reverse does not hold: difficulty does not imply universality. E.g. the fact that a problem cannot be solved in polynomial nondeterministic time does not imply that it is NP-complete (i.e. universal for NP).

For NP: if P=NP all problems except trivial ones will be complete for NP (under Karp reductions). So assume P is a proper subset of NP (or alternatively use a weaker notion of reduction like AC0).

Consider a unary language which is outside NP. (It is an easy exercise to show there are unary languages of arbitrary difficulty.) The language cannot be complete for NP by Mahoney's theorem.

$\endgroup$

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.