# Polynomial-time reduction of Primality and 3-SAT

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.

For the first question: This is an open problem. If $$\mathsf{P} \neq \mathsf{NP}$$ then the answer is no: the decision version of 3-SAT is $$\mathsf{NP}$$-Complete, while Primality is in $$\mathsf{P}$$, the means that a Karp reduction from 3-SAT to Primality would imply $$\mathsf{P}=\mathsf{NP}$$.

For the second question: Primality is in $$\mathsf{P} \subseteq \mathsf{NP}$$, therefore there is a Karp reduction from Primality to any $$\mathsf{NP}$$-Complete problem, such as 3-SAT.