principleMinor
Is this language depending on P = NP recursive?
Viewed 0 times
thisdependingrecursivelanguage
Problem
Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language
$$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$
A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?
$$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$
A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?
Solution
If P=NP, then $L = (0+1)^*$ which is regular grammar. Hence, it is recursive.
If P!=NP, then $L = \phi $ which is also a regular grammar. Hence, recursive.
In both the cases, $L$ will be a recursive language.
PS I see a lotta GATE problems these days :D
If P!=NP, then $L = \phi $ which is also a regular grammar. Hence, recursive.
In both the cases, $L$ will be a recursive language.
PS I see a lotta GATE problems these days :D
Context
StackExchange Computer Science Q#22017, answer score: 7
Revisions (0)
No revisions yet.