NVS PGT CS 2017 Part-B
December 16, 2023GATE 2003
December 16, 2023GATE 2003
| Question 13 |
Nobody knows yet if P = NP. Consider the language L defined as follows:
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 recursive or not will be known after we find out if P = NP |
Question 13 Explanation:
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.
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.
Correct Answer: A
Question 13 Explanation:
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.
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.