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.
2 Answers
$\begingroup$
$\endgroup$
3
Yes, they can since $P \subseteq NP$.
-
$\begingroup$ Exercise: Does $NP \subseteq P$ hold? $\endgroup$– user99558Commented Mar 4, 2019 at 0:23
-
-
$\begingroup$ @SiluPanda "⊆" means "subset of or equal to". $\endgroup$– GeremiaCommented Sep 16, 2023 at 21:33
$\begingroup$
$\endgroup$
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.
