Let $O$ be an optimisation problem and $P$ its decision variant. I know that $O$ is said to be NP-hard if $P$ is $NP-$complete. However, what to say about $O$ when the decision problem $P$ is no more in the class $NP$, and thus it's no more $NP-$complete(the algorithm of deciding is pseudo-polynomial and there is no better alternatives)?

  • 2
    $\begingroup$ I know that 𝑂 is said to be NP-hard if 𝑃 is 𝑁𝑃−complete No. $NP$-hard means that every problem from $NP$ is polynomially reducible to this problem. It doesn't mean that its decision problem is $NP$-complete (i.e. lies in $NP$). $\endgroup$
    – user114966
    Aug 20, 2020 at 23:53
  • $\begingroup$ Please check xlinux.nist.gov/dads/HTML/nphard.html, "When a decision version of a combinatorial optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard. " $\endgroup$
    – Best_fit
    Aug 21, 2020 at 0:04
  • 2
    $\begingroup$ The wording matters. "$X$ is said to be $Y$ when $Z$" is a definition of $Y$. The citation you've shared means implication: "when $Z$, then $Y$" - which means that $Z$ doesn't have to hold for $Y$ to be true. In this case, it's not necessary for decision problem to be NP-complete, for the optimization problem to be NP-hard. $\endgroup$
    – user114966
    Aug 21, 2020 at 1:17
  • $\begingroup$ @Dimitry it seems that your comments starts to constitute an answer. Maybe you would like to get actual upvote? $\endgroup$
    – Evil
    Aug 21, 2020 at 2:07


Your Answer

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

Browse other questions tagged or ask your own question.