in Theory of Computation edited by
33 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$
in Theory of Computation edited by

1 comment

computational classes is in syllabus???

Subscribe to GO Classes for GATE CSE 2022

4 Answers

41 votes
Best answer

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


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
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
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.
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 ...
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.
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$.
But Recursive language is not close under Emptiness.

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.

reshown by
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
7 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 

1 comment

 Gate Ranker18 

but finiteness roblem is undecidable for recursive 

2 votes
n both case(P = NP or P != NP) L is regular, so L is recursive.

Hence A is the answer
1 vote
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.

Related questions