2
$\begingroup$

Prove that $L$ is closed under Kleene star iff $L=NL$

Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$. Lets consider language $A\in L$. We show that also $A^*\in L$. It is easy because we can guess partition of word $w=w_1w_2..w_k$ and launch algorithm for each part. It is possible because $L=NL$ so being in class $L$ we can use guessing.

However, when we assume that $L$ is closed under Kleene star I am hopeless. Obviously, from assumption we know that $A\in L$ then also $A^*\in L$. Of course, we know that $L\subseteq NL$. However I must now show that $NL\subseteq L$ using assumption. This is hard for me.

$\endgroup$
3
  • 1
    $\begingroup$ Some questions are supposed to be hard. $\endgroup$ Aug 16, 2017 at 19:31
  • $\begingroup$ @YuvalFilmus Do you mean $A^* \in L \Rightarrow NL \subseteq L$ part? $\endgroup$
    – fade2black
    Aug 16, 2017 at 19:34
  • $\begingroup$ Yes, that's the non-trivial part of this exercise. $\endgroup$ Aug 16, 2017 at 19:35

1 Answer 1

3
$\begingroup$

Let $A$ be the language consisting of the following words: $$ (u,v)|\Sigma^*|(v,w), $$ where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.

Given a directed graph $G$, we can encode it as a list of edges in the following way: $$ (x_1,y_1)(x_1,y_1)|(x_2,y_2)(x_2,y_2)|\cdots|(x_m,y_m)(x_m,y_m) $$ where $x_i,y_i$ are vertex numbers encoded in binary. Furthermore, this string, which we denote by $\langle G \rangle$, can be output by a logspace machine.

Suppose now that we are given two vertices $s,t$, and that there is an $s$-$t$ path of length $\ell$ of the form $(s,x),\ldots,(y,t)$ in $G$. Then I claim that for all $L \geq \ell$, $$ (s,x)|\langle G \rangle^L|(y,t) \in A^*. $$ Conversely, if such a string belongs to $A^*$ then there is an $s$-$t$ path in $G$. In other words, $$ \exists \text{$s$-$t$ path in $G$} \longleftrightarrow (s,t) \in G \lor \exists x,y \text{ s.t. } (s,x)|\langle G \rangle^n|(y,t) \in A^*. $$

If we assume that $\mathsf{L}$ is closed under Kleene star then $A^* \in \mathsf{L}$, and so we can evaluate the right-hand side formula in logspace. Since $s$-$t$ reachability is $\mathsf{NL}$-complete, we deduce that $\mathsf{L}=\mathsf{NL}$.

$\endgroup$
1
  • $\begingroup$ Ok, I will read it later and accept (and possibly ask questions in comments in case of problems with understanding). Before that, I would like to think more about this exercise - maybe I defeat it on my own. Could you edit and add hints (something like step by step hidden under spoiler) ? I know that you show solution and it is nice. However, beside solution you can add also hints step by step - it will be educationally valuable. $\endgroup$ Aug 16, 2017 at 20:13

Your Answer

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

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