I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NL-C languages would produce a language not necessarily in NL-C. Is it also true that NL-C languages are not closed under the complement, concatenation, and star operations?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
NL-complete languages are in fact closed under complementation. This is not trivial at all and follows from the famous Immerman-Szelepcsényi theorem, which asserts NL = co-NL. (The proof is short but ingenious; the theorem earned Immerman and Szelepcsényi the Gödel prize.) The complement of an NL-complete language is co-NL-complete, and therefore NL-complete by NL = co-NL.
Other than that, NL-complete languages aren't closed under most of the operations you mention. Usually, intersection, union and other kinds of operations commonly considered in the context of formal languages aren't very interesting in the context of complexity theory.
- NL-complete languages are not closed under intersection: take your favorite NL-complete language and just intersect it with its complement, which yields the empty language.
- Not closed under union: unite your favorite NL-complete language with its complement, yielding the language of all words.
- Not closed under Kleene star: Take your favorite NL-complete language on $\{a, b\}$ and add the one-letter words $a$ and $b$ into it; it remains NL-complete (an easy exercise), and the Kleene star gives the language of all words.
A word about concatenation. If $L$ and $L'$ are NL-complete, then $L ⋅ L'$ is in NL (there is a nondeterministic logspace algorithm which guesses the separation then checks the two pieces for membership in $L$ and $L'$). If we want to find an example where $L ⋅ L'$ is not NL-complete, we need some NL language which is not NL-complete. The only languages that we know to have this property are the empty language and the language of all words, because it is unknown whether L = NL (although most people conjecture L ≠ NL), and if L = NL then any non-trivial problem in NL is actually NL-complete. So, to find a counterexample, we have to arrange so that $L ⋅ L' = Σ^*$. That's probably not hard to do (leaving that as an exercise since I'm running out of time).
