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?

  • $\begingroup$ 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. $\endgroup$ – 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).

  • $\begingroup$ Oh I see! Thank you so much for the clearness! I thought that whenever I have to approach questions like these I have to keep in mind that P is always not equal to NP, my bad! $\endgroup$ – user2256 Aug 5 '17 at 9:46
  • $\begingroup$ So if I'm asked what is the smallest class that this language is in then RE it is? $\endgroup$ – user2256 Aug 5 '17 at 9:50
  • $\begingroup$ The smallest class that contains this language is clearly $\{L\}$. $\endgroup$ – Yuval Filmus Aug 5 '17 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.