# What to say if a decision problem is not NP?

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)?

• 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$).
– user114966
Aug 20, 2020 at 23:53
• 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. " Aug 21, 2020 at 0:04
• 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.
– user114966
Aug 21, 2020 at 1:17
• @Dimitry it seems that your comments starts to constitute an answer. Maybe you would like to get actual upvote?
– Evil
Aug 21, 2020 at 2:07