Complejidad computacional versus jerarquía Chomsky

Me pregunto sobre la relación entre la complejidad computacional y la jerarquía de Chomsky, en general.

En particular, si sé que algún problema es NP-completo, ¿se deduce que el lenguaje de ese problema no está libre de contexto?

Por ejemplo, el problema de la camarilla es NP-completo. ¿Se deduce que el lenguaje correspondiente a modelos con camarillas es de una complejidad mínima en la jerarquía de Chomsky (para todas / algunas formas de codificar modelos como cadenas?)

Hay cuatro clases de lenguaje en la jerarquía de Chomsky:

1. $\mathrm{TIME}(n)$$\mathrm{TIME}(o(n\log n))$$\mathrm{SPACE}(0)$$\mathrm{SPACE}(o(\log\log n))$

2. $\mathrm{LOGCFL}$$\mathrm{LOGCFL}$$\mathrm{AC}^1$$\mathrm{P}$

3. $\mathrm{NSPACE}(n)$

4. Gramáticas sin restricciones: esta clase consta de todos los lenguajes recursivamente enumerables.

$\neq$