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.


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.


Your Answer

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

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