Recursive-Enumerable-Languages
Question 1 |
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 1 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.