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?)

  • $\begingroup$ 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".... $\endgroup$
    – vzn
    May 20, 2014 at 23:38

1 Answer 1


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.

  • $\begingroup$ There are plenty of nonregular linear-time languages. You probably meant SPACE(0) or SPACE(o(log log n)). $\endgroup$ May 21, 2014 at 9:57
  • $\begingroup$ (Or a nonstandard definition of $\mathrm{TIME}(f(n))$ such as using single-tape machines.) $\endgroup$ May 21, 2014 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.