Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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 four classes of language in the Chomsky hierarchy:
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).
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.
Context-sensitive languages — this class corresponds to $\mathrm{NSPACE}(n)$.
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.
