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$

migrated from ai.stackexchange.com Mar 3 at 23:18

This question came from our site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment.

2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Exercise: Does $NP \subseteq P$ hold? $\endgroup$ – KVN Mar 4 at 0:23
  • $\begingroup$ Isn't this a open problem? $\endgroup$ – SiluPanda Apr 24 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