# Recusively Enumerable or Recursive dependent on whether P=NP

If a language is defined such that
$L = (0+1)^{\ast}$ if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$ otherwise

Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the empty langauge. Therefore $\mathsf{P} = \mathsf{NP}$ , $L$ is recursive (being regular), but is $L$ still recursive if $\mathsf{P} \neq \mathsf{NP}$?

-

## migrated from cstheory.stackexchange.comJan 10 '13 at 2:47

This question came from our site for theoretical computer scientists and researchers in related fields.

Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. We have migrated your question to Computer Science which has a broader scope. – Kaveh Jan 10 '13 at 2:47
In both cases L is regular ans thus recursive. – Ran G. Jan 10 '13 at 4:22
@Ran G. Turn into an answer? – Yuval Filmus Jan 10 '13 at 11:35

The language $L = \emptyset$ is indeed a recursive set.