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.

  • 3
    $\begingroup$ Cross-posted to math.se. Cross-posting is frowned upon on StackExchange since the moment an answer is posted on one site, it could make all the effort after that on another site essentially wasted. Not all users of cs.se read the posts on math.se and vice versa so there's a good chance that a stellar answer on one site might remain unseen on another. Better to ask a question in one place and then if no answer is forthcoming on that site, delete the question and ask it again on the other. $\endgroup$ – Rick Decker Jun 8 '16 at 0:22

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.


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++$:

    1. For $j=1; j\leq n, j++$:
      1. 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$.


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

  • 1
    $\begingroup$ Your answer is very hard to read. Try formatting it better. $\endgroup$ – Yuval Filmus Jan 22 '17 at 8:59
  • $\begingroup$ This seems correct but it's barely readable. $\endgroup$ – David Richerby Jan 22 '17 at 10:28

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.