Nobody knows yet if P = NP. Consider the language L defined as follows : Which…
2003
Nobody knows yet if P = NP. Consider the language L defined as follows :
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 recursive or not will be known after we find out if P = NP
Attempted by 8 students.
Show answer & explanation
Correct answer: A
The language L is defined as (0+1)* if P = NP, otherwise the empty set. Since both (0+1)* and the empty set are regular languages, they are also recursive. Therefore, regardless of whether P = NP is true or false, L is always a recursive language. This means that statement A (L is recursive) must be true.