13
$\begingroup$

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

$\endgroup$
  • $\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 '14 at 23:38
11
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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