<p>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").</p>

<p>Due to the NP completeness of the 3-SAT problem, I think your question:</p>

<ul>
<li>is Primality ≤p 3-SAT</li>
</ul>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2020-05-20T09:27:35.863Z
2020-05-20T09:27:35.863Z
nick
<p>Is 3-SAT <span class="math-container">$\leq_{p}$</span> Primality? And/or is Primality <span class="math-container">$\leq_{p}$</span> 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.</p>

<p>Thank you.</p>

<np-hardness><np-complete><np>
Polynomial-time reducibility of Primality and 3-SAT
oompa
# Polynomial-time reducibility of Primality and 3-SAT

(Asked by: username_0 on 2020-05-19)

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.

**Tags:** np-hardness, np-complete, np


---

## 1 answers

### Answer by username_1 on 2020-05-20. Score: 1

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.


---

