Recursive languages , please check whether my explain is correct?

62 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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