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? $L$ is recursive $L$ is recursively enumerable but not recursive $L$ is not recursively enumerable Whether $L$ is recursively enumerable or not will be known after we find out if $P=NP$ Theory of Computation gatecse-2003 theory-of-computation normal recursive-and-recursively-enumerable-languages + – Kathleen asked Sep 16, 2014 edited Feb 28, 2018 by kenzou Kathleen 9.5k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply mrinmoyh commented Aug 26, 2019 reply Follow Share computational classes is in syllabus??? 1 votes 1 votes Rusty_01 commented Jun 6, 2022 reply Follow Share how L = {} or L = Φ Whether, L is decidable or undecidable.Depends on the domain of the problem. But here they are asking for a specific problem. And we can always create TM for specific problems. So, that’s why it is Recursive language. 0 votes 0 votes Please log in or register to add a comment.
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. Arjun answered Sep 27, 2014 edited May 6, 2021 by soujanyareddy13 Arjun comment Share Follow See all 10 Comments See all 10 10 Comments reply anonymous commented Dec 24, 2014 reply Follow Share why not option d) in question its mentioned it i/> so after we know that p = np then only we can say L is recursive 0 votes 0 votes anonymous commented Dec 24, 2014 reply Follow Share why not option d) in question its mentioned it is not yeD so after we know that p = np then only we can say L is recursive 0 votes 0 votes Arjun commented Dec 24, 2014 reply Follow Share Yes. 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. 38 votes 38 votes Vaishali Trivedi commented Oct 7, 2016 reply Follow Share there are two conditions - 1 when p=np then turing machine accept language (a+b)* or if not then empty string. 2 when turing machine is accepting (a+b)* then p=np and empty string then p != np . my question is that what question is asking for 1st condition or 2nd condition. please explain ... 0 votes 0 votes Prashant. commented Oct 7, 2016 reply Follow Share Quetion is saying ( asking what is L language) if p=np( which is till now not solve ie. we dont know either it is yes or no) then L= (a+b)* else L = phi here condition dont matter in problem B/ c either it is true or false language is always regular. Since (a+b)* and Phi both are regular , and since regular are subset of recusive which is decidable. 21 votes 21 votes Sachin Mittal 1 commented Dec 27, 2016 reply Follow Share It is not the job of TM to decide If $P=NP$ or not. Job of TM is to decide language, that language is $(0+1)^*$ or $\phi$. 18 votes 18 votes Brij Mohan Gupta commented Jul 15, 2017 reply Follow Share But Recursive language is not close under Emptiness. 0 votes 0 votes Rupendra Choudhary commented Nov 1, 2017 reply Follow Share 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. 0 votes 0 votes raghuponnan commented Dec 19, 2018 i reshown by raghuponnan Aug 22, 2019 reply Follow Share Here we have considered two options P=NP or P!=NP. In Both cases the answer is recursive. But what happens if P=NP problem is undecidable 0 votes 0 votes ankit3009 commented Nov 19, 2021 reply Follow Share As here we are provided with a simple if logic program, which is surely going to halt(we have covered both valid and invalid string logic). That’s the reason, it’s recursive, right ? 0 votes 0 votes Please log in or register to add a comment.
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 Gate Ranker18 answered Sep 3, 2017 Gate Ranker18 comment Share Follow See 1 comment See all 1 1 comment reply set2018 commented Nov 2, 2017 reply Follow Share Gate Ranker18 but finiteness roblem is undecidable for recursive 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes n both case(P = NP or P != NP) L is regular, so L is recursive. Hence A is the answer Regina Phalange answered Apr 13, 2017 Regina Phalange comment Share Follow See all 0 reply Please log in or register to add a comment.
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. keshore muralidharan answered Aug 16, 2020 keshore muralidharan comment Share Follow See all 0 reply Please log in or register to add a comment.