Is it a sufficient condition to be in NP?

Question

Suppose the following situation.

• You have a decision problem $D$.
• You know that $SAT$ is $NP$-complete.
• You know that $D\leq_p SAT$.

Can you conclude that $D\in NP$?

I think it's true because it means that $D$ is at least as hard as any other problem in $NP$.

As I know I am not able to post questions to answer with yes/no: If it's true, can you give a better explanation? If it's false, can you argue why is so?

PD: it's not homework.

Answer 1

You can obtain a non-deterministic polynomial-time Turing machine $T$ for $D$ as follows:

• Since $D \le_p SAT$, there is a polynomial-time Turing machine $T'$ that maps any instance of $D$ into an instance of $SAT$. Simulate the $T'$ on $x$, where $x$ is the input of $T$.
• Use any non-deterministic polynomial-time algorithm to decide SAT (e.g., guess the value of all the variables in the SAT formula and check if the formula is satisfied). By definition of Karp reduction, $T$ will accept if and only if $x \in D$.

This shows that $D \in \mathsf{NP}$.