1
$\begingroup$

I know that NP problems can be transformed into SAT (due to this fact, SAT is considered to be a NP Complete problem). I am not sure if P problems can too be transformed into SAT.

$\endgroup$
2
$\begingroup$

Yes, they can since $P \subseteq NP$.

$\endgroup$
  • $\begingroup$ Exercise: Does $NP \subseteq P$ hold? $\endgroup$ – KVN Mar 4 '19 at 0:23
  • $\begingroup$ Isn't this a open problem? $\endgroup$ – SiluPanda Apr 24 '19 at 5:25
0
$\begingroup$

Yes, it can because P class is included in NP class, you can convert every P problem into 3-SAT in (at most) polynomial time.

$\endgroup$

Your Answer

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