# Computational complexity vs. Chomsky hierarchy

I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general.

In particular, if I know that some problem is NP-complete, does it follow that the language of that problem is not context-free?

For example, the clique problem is NP-complete. Does it follow that the language corresponding to models with cliques is of some minimal complexity in the Chomsky hierarchy (for all/some ways of encoding models as strings?)

• there are many subtle interrelationships but they are mostly orthogonal concepts. basically different problems about each language class can have different complexities. as for NP completeness there is a theorem about "sparse languages".... – vzn May 20 '14 at 23:38

There are four classes of language in the Chomsky hierarchy:

1. Regular languages — this class is the same as $\mathrm{TIME}(n)$ or $\mathrm{TIME}(o(n\log n))$ (defined using single-tape machines, see Emil's comment), or $\mathrm{SPACE}(0)$ or $\mathrm{SPACE}(o(\log\log n))$ (per Emil's comment).

2. Context-free languages — this class doesn't have nice closure properties, so instead one usually considers $\mathrm{LOGCFL}$, the class of languages logspace-reducible to context-free languages. It is known that $\mathrm{LOGCFL}$ lies in $\mathrm{AC}^1$ (and so, in particular, in $\mathrm{P}$), and it has nice complete problems detailed in the linked article.

3. Context-sensitive languages — this class corresponds to $\mathrm{NSPACE}(n)$.

4. Unrestricted grammars — this class consists of all recursively enumerable languages.

If a language in NP-complete then assuming P$\neq$NP, it is not context-free. However, it could be context-sensitive (clique and SAT both are). Any language in NP is described by some unrestricted grammar.

• There are plenty of nonregular linear-time languages. You probably meant SPACE(0) or SPACE(o(log log n)). – Emil Jeřábek May 21 '14 at 9:57
• (Or a nonstandard definition of $\mathrm{TIME}(f(n))$ such as using single-tape machines.) – Emil Jeřábek May 21 '14 at 11:02