Show that P is closed against the Kleene star

Question

I have that question that looks kinda easy at first but it is quite hard.

Let $L\in P$. Prove that $L^*\in P$

my approach:

I tried to generate a Turing machine but I got stuck with the thing of the poly time machine, I only managed to create a non-deterministic machine. I know that there is a complicated method with graphs or with dynamic programming, But I am asking for a full proof or a more gentle one, "computational models"-oriented and not with algorithmic approach, but both kinds of proof will be good.

Answer 1

Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial time.

Answer 2

Let $R$ be a polynomial-time decider for $L$. Construct a deterministic Turing machine $M$ that decides $L^*$.

$M =$ "on input $w=w_1...w_n$:

1. Initialize a directed graph $G$ with $n$ nodes.

2. For $i=1; i\leq n; i++$:

   3. For $j=1; j\leq n, j++$:
      4. Run $R$ on $w_i...w_j$. If $R$ accepts, add a vertex from node $i$ to node $min(j+1,n)$ of $G$.

3. Run any polynomial-time graph search on $G$ to find a path from node $1$ to node $n$. Accept if any exists. Else, reject."

Because we can construct a polynomial-time decider for $L^*$, $L^* \in P$.

Answer 3

Let w=x1..xn be a word over some alphabet. Consider all options of continuous subwords of w. we have to choose the left index := i and the right index := j (which can be the same).

In total we have n choose 2 (if i!=j) + n (if i=j) subwords. any way this is bounded by n^2. we can check in polynomial time for each i,j (j>=i) if xi..xj∈L. and because we have at most n^2 subwords we can check it for all i,j in polynomial time.

Now the tricky part: consider the directed graph:

G. G = (V,E) V = { [i,j] | xi..xj∈L} U {v1,vn} (we add 2 more vertex v1 and vn, you will see why in a minute).

E = {(v1,[1,j]) | [1,j]∈V} U {([i,n],n) | [i,n]∈V} U {([i,j][j+1,k]) | [i,j],[j+1,k]∈ V}

Now check if G has a directed path from v1 to vn in polynomial time. (BFS / DFS starting at v1). it easy to see G