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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ No. You should probably refer to the explicit definition of NP-hardness. Hint: consider problems in coNP. $\endgroup$– mdxnCommented Dec 16, 2014 at 7:05
-
$\begingroup$ @mdx - for all we know, problems in coNP might also reside in NP. $\endgroup$– A ACommented Dec 16, 2014 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$– mdxnCommented Dec 16, 2014 at 7:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Dec 16, 2014 at 7:10
-
$\begingroup$ I agree, but I'm wondering if this can be shown false without any unknown assumptions. $\endgroup$– A ACommented Dec 16, 2014 at 7:27
$\begingroup$
$\endgroup$
3
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.
-
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$ Commented Jun 29, 2015 at 6:01
-
2$\begingroup$ Especially, please stop adding negative spaces, which cause characters to run into each other. $\endgroup$ Commented Jun 29, 2015 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$– JuhoCommented Jun 29, 2015 at 6:09
$\begingroup$
$\endgroup$
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.
