Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
Add a comment
|
$\begingroup$
$\endgroup$
Probably you mean "Prime" with "Primality" (i.e. to know if a number is prime or not, which is in P :see the AKS article "Prime is in P").
Due to the NP completeness of the 3-SAT problem, I think your question:
- is Primality ≤p 3-SAT
has TRUE like an answer, like you think. In fact every problem in NP can be reduced to 3-SAT in polynomial time, so every problem in P also, because every language in P is also in NP.
The other statement, 3-SAT ≤p Primality, would imply Primality to be NP-Complete and is not know for the moment. Anyway IF SO, P = NP because Primality is NP-Complete and Primality is in P.
