0
$\begingroup$

From Cook & Levin's theorem we know that all Problems in NP are polynomially reducible to SAT: $ \forall_{L\in NP}: L \leq_{p}SAT$.

Is the opposite also true? That is if we know that a language L is reducible to SAT in polynomial time, can it be also stated that it must be in NP?

$L \leq_{p}SAT \Rightarrow L \in NP$

I am struggling to understand if this holds true.

$\endgroup$

2 Answers 2

1
$\begingroup$

Yes, this is true. More generally, if $A \le_p B$ and $B \in \mathbf{NP}$, then $A \in \mathbf{NP}$. (Most intro theory textbooks include a proof of this result.)

In fact, one way of defining what the class $\mathbf{NP}$ is is as “the class of all decision problems that polynomial-time reduce to $SAT$.”

$\endgroup$
1
$\begingroup$

Yes, it is true, and to get a feeling for why it is so, we can appreciate the fact that a reduction is just an algorithm (in this case, a poly-time algorithm) that transforms instances of one problem into instances of another.

So, given a string $x$, one way to check if $x \in L$ is to run the reduction to SAT (in polynomial time) on $x$ and check if the resulting formula is satisfiable (in non-deterministic polynomial time). This is clearly a non-deterministic poly-time algorithm to check membership in $L$; in other words, $L$ is in $NP$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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