# Proving that the set of non-universal CFGs is not in NP

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.
• 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. – Moshe Hoori Dec 16 '14 at 6:06
• 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? – Moshe Hoori Dec 16 '14 at 11:42