# Is it a sufficient condition to be in NP?

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.

## 1 Answer

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}$$.