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?
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.
if P=NP problem becomes decidable then L will becomes Regular.
if we don't know whether P=NP or not , we can't comment about regularity but at least we can say L is REC at least.
(0+1)* and ∅ both are regular , means there won't be any possibility of TM hang (looping) and in that we we can design algo for L. so with this argument L=REC.
tell me if someone find anything wrong in my arguments.
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
Gate Ranker18
but finiteness roblem is undecidable for recursive
64.3k questions
77.9k answers
243k comments
79.7k users