How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where

$\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$


Hint: Use the fact that universality of context-free grammars (that is, deciding whether $L(G) = \Sigma^*$) is undecidable.

  • $\begingroup$ I thought it has something to do with proving $ALL_{CFG}$ is undecidable. But I don't know how to get from there to proving that it is not an NP problem. $\endgroup$ – Moshe Hoori Dec 16 '14 at 6:06
  • $\begingroup$ Well, keep trying. $\endgroup$ – Yuval Filmus Dec 16 '14 at 6:08
  • $\begingroup$ I'm not sure but this is what I come up with so far: $ALL_{CFG}$ is undecidable so $\overline{ALL_{CFG}}$ is undecidable too. undecidable languages can't be NP. is that right? $\endgroup$ – Moshe Hoori Dec 16 '14 at 11:42
  • $\begingroup$ Yes, that's the idea. Make sure that you understand why undecidable languages are not in NP. $\endgroup$ – Yuval Filmus Dec 16 '14 at 17:00

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.