# Prove the recursive enumerability of the class of NP-hard context-free languages

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?

• First, note that P is a subset of RE. Second, there is no obvious connection between the fact that the word problem for CFGs has an efficient solution and the problem at hand. I suggest reviewing the definitions involved. – Yuval Filmus Aug 5 '17 at 9:22

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).
• The smallest class that contains this language is clearly $\{L\}$. – Yuval Filmus Aug 5 '17 at 9:51