Reductions to and from PRIME

Question

I think PRIME (is the given number a prime number?) is a good example a decision problem. Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to PRIME.

What are decision problems that can be reduced to PRIME, and how do these reductions look like?

What are decision problems that PRIME can reduce to, and how do these reductions look like?

Answer 1

Assuming you're talking about polynomial-time reductions, since PRIME is in $P$, you can reduce it to any non-trivial decision problem (for which there is at least one instance with answer YES and at least one instance with answer NO). Moreover, any problem in $P$ can be reduced to PRIME.

To reduce an instance $I$ of PRIME to an instance $I_Q$ of non trivial decision problem $Q$, let $Y_Q$ and $N_Q$ be a YES and a NO instance for $Q$, respectively. The reduction is as follows: solve $I$ using a polynomial-time algorithm for PRIME. Then, let

$$I_Q = \begin{cases}Y_Q & \mbox{if $I$ is a YES instance}, \\ N_Q & \mbox{if $I$ is a NO instance}.\end{cases}$$

To reduce an instance $I_Q$ of a problem $Q \in P$ to an instance $I$ of PRIME, solve $I_Q$ using a polynomial-time algorithm for $Q$ and define

$$I = \begin{cases}2 & \mbox{if $I_Q$ is a YES instance}, \\ 1 & \mbox{if $I_Q$ is a NO instance.}\end{cases}$$