Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.

$$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$

Which of the following statements is true?

  1. $L$ is recursive
  2. $L$ is recursively enumerable but not recursive
  3. $L$ is not recursively enumerable
  4. Whether $L$ is recursively enumerable or not will be known after we find out if $P=NP$

I try to explain

(1) $L$ is recursive. If $P=NP$, $L$ is $\Sigma^*$ which is recursive (in fact regular). If not, $L = \phi$ which is again recursive. So, in both cases $L$ is recursive.

We don't know if P = NP. But either P = NP, or P ≠ NP. In both the cases L is recursive.

If L was non-recursive for either P = NP, or P ≠ NP, then we would have to wait till the solution of P = NP, to say if L is recursive or not.


You are absolutely correct: although we don't know which program computes $L$, we know that there is a program which computes $L$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.