Problem Detail: 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?)
Asked By : sjmc
Answered By : Yuval Filmus
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(nlog n))$ (defined using single-tape machines, see Emil’s comment), or $mathrm{SPACE}(0)$ or $mathrm{SPACE}(o(loglog 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/25940
