edited by
9,488 views
38 votes
38 votes

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & 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$
edited by

4 Answers

Best answer
51 votes
51 votes

Correct Option: A

$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.

edited by
8 votes
8 votes

we have two problems one is P and another is NP
now we give these 2 problems to TM then acc to condition given if both P and NP are equal then it will give (0+1)∗ otherwise ϕ , not others will be given 
so we make total TM for this becoz it say "YES" or "NOT", never fall into loop
and if we make Total TM for language then that language is recursive
hence Ans is A 

2 votes
2 votes
Here, we have two possibilities, whether
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is regular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Answer:

Related questions