Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I was asked to prove that the next language is recursive enumerable :
$$L= \{ \langle G \rangle \mid SAT<L(G) \} $$
where $G$ is a context free grammar and there is a polynomial reduction from the SAT problem to the language that's accepted by $G$.
I can't seem to understand why this problem is in RE. Isn't determining whether a word is accepted by a certain CFG done in a polynomial time? What am I missing here?
You should distinguish between two cases. If $\mathsf{P} \neq \mathsf{NP}$ then $L(G)$ cannot be $\mathsf{NP}$-hard since $L(G) \in \mathsf{P}$. In this case, $L = \emptyset$.
Conversely, if $\mathsf{P} = \mathsf{NP}$, then all non-trivial languages in $\mathsf{P}$ are $\mathsf{NP}$-hard. In this case, $L = \{ \langle G \rangle : L(G) \neq \emptyset, \Sigma^* \}$. It is possible to decide whether $L(G) \neq \emptyset$, and the problem of determining whether $L(G) \neq \Sigma^*$ is clearly r.e. (in fact, it is $\Sigma_1$-complete), and so $L$ is r.e. (in fact, $\Sigma_1$-complete).
