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

If it had been given that L is set of RE Language, then for this ques Ans had been being RE but not REC.

---

The condition P=NP can be replaced with "Find a grammar L is ambiguous or not", in accordance with the syllabus. The answer would be same

---

To anyone who is wondering, this question is not at all asking anything about $\text{P}$ and $\text{NP}$. They may give any mathematical conjecture instead of famous "$\text{P=NP?}$" conjecture. Without the knowledge about $\text{P}$ and $\text{NP}$, you can solve this GATE question.

Consider the variation of this question which I have taken from Rice University pdf - 

$L_{52}$ is decidable because whether $ \text{God exists or not} $, $L_{52}$ will anyways be finite and therefore regular (decidable too). You don't need to know anything about existence of $\text{God}$ to solve this question.

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

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 ?

---

This comment was originally defending option D. But I have realized a mistake in my solution. The answer is indeed A.

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 

---

@set2018 if i gave you L1 = sigma* 

and i asked what is the language type??

you will tell regular because there exist DFA, NFA, regular expression, you won't be checking whether the regular languages are decidable or undecidable for universality problem

similarly for L2 = Pi you won't check whether regular langs are decidable on emptiness or not...

like wise if i gave you L3 .. you can say it is REC if there exist an HTM.. you won't check the acceptance / finiteness to the REC lang...

they are just asking what is the language type that's it.. no decidable undecidable check needed until they ask for it

Answer 3

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 4

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

Hence A is the answer

Answer 5

The answer is A. There are two turing machines one which accepts (a+b)* and one which accepts {} one of them is correct. We don't need to know which one is correct, but as we can see one does exist.

Answer 6

The correct statement is A. $L$ is recursive.

Here is the reasoning:

1. The $P \text{ vs } NP$ problem is a mathematical statement that is either true or false. It is a fixed, but unknown, answer.

2. This means the language $L$ is one of two specific languages; we just don't know which one. We must analyze both possibilities:

   • Case 1: Assume $P = NP$ is true.

     In this case, the language is $L = (0+1)^*$, which is the set of all possible strings. This is a regular language. Every regular language is also recursive (decidable). A Turing machine can easily decide this by immediately halting and accepting any input.

   • Case 2: Assume $P \ne NP$ is true.

     In this case, the language is $L = \emptyset$, the empty language. This is also a regular language. Every regular language is recursive. A Turing machine can decide this by immediately halting and rejecting any input.

Since $L$ is recursive in both possible scenarios, $L$ is, by definition, a recursive language. We don't need to know the answer to $P \text{ vs } NP$ to know that $L$ is decidable; we know that whatever $L$ turns out to be, it's one of two languages that are both decidable.