5
$\begingroup$

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.

$\endgroup$
1
  • 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$ Commented Jun 8, 2016 at 0:22

4 Answers 4

11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

Just extending a bit more what Yuval Filmus has already said. Suppose your input is $x_1\ldots x_n$.

Let's use a memorization array $A$, where $A[i]$ is $True$ in case $x_1 \ldots x_i$ is in $L^*$ and is $False$ otherwise.

Consider the deterministic Turing machine $M$ that does the following:

  1. Set $A[0]$ to $True$, since the empty string $\epsilon$ is in $L^*$.
  2. Compute $A[i]$ bottom-up. If there is some $j$ with $0 \leq j < i$ such that $A[j] = True$ (i.e. $x_1 \ldots x_j \in L^*$) and $x_{j+1} \ldots x_i$ is in $L$, set $A[i] = True$. Put $A[i] = False$ otherwise. Do that for every $i$, starting at $1$ and ending at $n$. Notice that this step can be done in polynomial time, because we can decide in polynomial time whether $x_{j+1}\ldots x_i$ is in $L$ ($L$ is in $P$ by hypothesis).
  3. If $A[n] = True$, accept. Otherwise, reject.
$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Your answer is very hard to read. Try formatting it better. $\endgroup$ Commented Jan 22, 2017 at 8:59
  • $\begingroup$ This seems correct but it's barely readable. $\endgroup$ Commented Jan 22, 2017 at 10:28
0
$\begingroup$

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$.

$\endgroup$

Your Answer

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

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