TIFR CSE 2021 | Part B | Question: 4

Question

Consider the following two languages.

$\begin{array}{rcl} \text{PRIME} &  = & \{ 1^{n} \mid n \text{ is a prime number} \}, \\ \text{FACTOR} &  = & \{ 1^{n}0 1^{a} 01^{b} \mid n \text{ has a factor in the range }[a,b] \} \end{array}$.

What can you say about the languages $\text{PRIME}$ and $\text{FACTOR}$?

• A. $\text{PRIME}$ is in $\text{P}$, but $\text{FACTOR}$ is not in $\text{P}$.
• B. Neither $\text{PRIME}$ nor $\text{FACTOR}$ are in $\text{P}$.
• C. Both $\text{PRIME}$ and $\text{FACTOR}$ are in $\text{P}$.
• D. $\text{PRIME}$ is not in $\text{P}$, but $\text{FACTOR}$ is in $\text{P}$.
• E. None of the above since we can answer this question only if we resolve the status of the $\text{NP}$ vs. $\text{P}$ question.

Answer 1

PRIME is in P :

References: AKS primality test

Primality testing with Gaussian periods

FACTOR is also in P :

Algorithm:

$ \text{if} \left (b-a +1 \right ) \geq n : \\ \qquad \text{return “Yes”} \\ \text{else if } (a\text{ mod }n ==0) \text{ or } (a\text{ mod }n > b\text{ mod }n )  : \\ \qquad \text{return “Yes”} \\ \text{else}: \\ \qquad \text{retrun “No”} $

Time complexity is $O(1)$ : polynomial time.

(C) is correct.