GATE CSE 2003 | Question: 13

Question

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?

• A. $L$ is recursive
• B. $L$ is recursively enumerable but not recursive
• C. $L$ is not recursively enumerable
• D. Whether $L$ is recursively enumerable or not will be known after we find out if $P=NP$

Comments

computational classes is in syllabus???

---

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.

Answer 1

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.

Comments

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.

---

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

---

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 ?

Answer 2

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 

Comments

 Gate Ranker18 

but finiteness roblem is undecidable for recursive 

Answer 3

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

Hence A is the answer

Answer 4

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.