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}$?
- $\text{PRIME}$ is in $\text{P}$, but $\text{FACTOR}$ is not in $\text{P}$.
- Neither $\text{PRIME}$ nor $\text{FACTOR}$ are in $\text{P}$.
- Both $\text{PRIME}$ and $\text{FACTOR}$ are in $\text{P}$.
- $\text{PRIME}$ is not in $\text{P}$, but $\text{FACTOR}$ is in $\text{P}$.
- None of the above since we can answer this question only if we resolve the status of the $\text{NP}$ vs. $\text{P}$ question.