0
$\begingroup$

Why isn't it possible to have P=NP, but not all problems in P are in NP-hard? The diagram of the various classes would look something like:

enter image description here

We have P=NP, but not all problems in P lie inside NP-hard. The intersection of P and NP-hard is still NP-complete.

Lander's theorem seemed relevant, but it holds when P != NP while my proposed scenario is for P=NP.

$\endgroup$
4
  • 1
    $\begingroup$ is your question "why does P=NP imply NP=NP-complete?" ? $\endgroup$
    – user126100
    Commented Oct 15, 2022 at 23:34
  • $\begingroup$ if that's the case, the implication is not true. Because of the counter-examples in @Arno's answer. what's true: is that every non-trivial set in P would be in NP-C and thus in NP hard. $\endgroup$
    – user126100
    Commented Oct 15, 2022 at 23:37
  • $\begingroup$ Yes, that's what my question boils down to. I think @benrg's answer clarifies this well. I still don't understand Arno's answer unfortunately. Still banging my head against it. But I feel good about excluding the trivial cases like you said. $\endgroup$ Commented Oct 16, 2022 at 0:17
  • $\begingroup$ for problem H, you have a function solveH(x). a problem is NP-Hard, if for every problem L in NP, you can find a polynomial-time function f such solveH(f(x)) solves L. for the problem "is x in the empty set?", you can't always find such a function. because no matter how you transform the input the answer would be always false. $\endgroup$
    – user126100
    Commented Oct 16, 2022 at 0:45

2 Answers 2

1
$\begingroup$

NP-hardness is technically defined in terms of Karp reduction, in which the answer to the target problem must be the answer to the source problem, and not in terms of Cook reduction, in which the target problem is used as an oracle. This means that the empty language and the language of all words aren't in NP-hard even if P=NP.

Excluding those trivial cases, every problem in P is polynomial-time reducible to every other problem in P, so if P=NP then every problem in NP is polynomial-time reducible to every problem in P (except those two), i.e., every problem in P (except those two) is NP-hard.

$\endgroup$
3
  • $\begingroup$ This answer is wrong. The only language reducible to $\emptyset$ is $\emptyset$ itself, and likewise, the only language reducible to $\Sigma^*$ is $\Sigma^*$ itself (due to a lack of positive/negative instances to map stuff to). $\endgroup$
    – Arno
    Commented Oct 16, 2022 at 0:08
  • $\begingroup$ We can think of those as trivial edge cases. If we exclude those, I think this answer works? $\endgroup$ Commented Oct 16, 2022 at 0:10
  • $\begingroup$ @Arno Yes, I was using an oracle notion of reducibility, which apparently is wrong. I updated the answer. $\endgroup$
    – benrg
    Commented Oct 16, 2022 at 0:41
2
$\begingroup$

Whether or not P is equal to NP, it is definitely not the case that P is a subset of NP-hard. This is because we know that $\emptyset$ and $\Sigma^*$ belong to P, but are not NP-hard.

$\endgroup$
10
  • $\begingroup$ What are $\emptyset$ and $\Sigma^*$? Any reference on them? $\endgroup$ Commented Oct 15, 2022 at 21:58
  • 1
    $\begingroup$ @RohitPandey the empty language and the language of all words. They are solved by the algorithms return false and return true respectively. $\endgroup$
    – Nathaniel
    Commented Oct 15, 2022 at 22:00
  • $\begingroup$ I'm not currently qualified to understand this since I never dug into the concept of languages and how they relate to sets of problems like P. I should do that and come back to this. $\endgroup$ Commented Oct 15, 2022 at 22:04
  • 1
    $\begingroup$ A language is a decision problem and a decision problem is a language. For a decision problem, the associated language is the set of positive instances of the problem. Also this contradict the question in the title: "why is $\mathsf{P}$ not contained in $\mathsf{NP}$-hard?" since those are problems (or languages) in $\mathsf{P}$ but not $\mathsf{NP}$-hard. $\endgroup$
    – Nathaniel
    Commented Oct 15, 2022 at 22:30
  • 1
    $\begingroup$ I understand now what you mean, but the answer is confusing. The question is "Why X?" and the answer has the form "Because [something that implies ¬X]". Also, I'm pretty sure OP is interested in why there can't be nontrivial members of P \ NP-hard. Your technical objection is correct, but probably should have been a comment. $\endgroup$
    – benrg
    Commented Oct 16, 2022 at 1:00

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.