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.


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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.