Show that PTIME and PSPACE is closed under Klenee star

1k Views Asked by At

how to show that PSPACE and PTIME are closed under Kleene star ? I can only show that NP is closed, but it is easy because we can use non-determinism to guess partition of word. In these two cases I don't have idea how to attack it.

Edit
Using @sdcvvc's hint.
Is obvious that when we build this graph the task is solved - it is because of the fact in linear time we check if there exists path from $1$ to $|w|$ where $w$ is input word.

So, how to build this graph in polynomial time and space ?
This building will be polynomial, lets consider position $i+1$, where for $1,2,3..,i$ . To build graph for $i+1$ we must (in pesimistic case) launch Turing machine for $L$ on words: $w[1,i+1], w[2,i+1],..,w[i,i+1]$. It consumes $(i+1)\cdot f(n)$ where $f(n)$ is polynomial. We can see that it is polynomial time and space.

1

There are 1 best solutions below

7
On BEST ANSWER

Hint: Consider a graph $G$ where vertices are positions in the word, and there is an edge $i \to j$ if the subword $w[i..j-1]$ is in $L$. Show that this graph can be computed in $PTIME$ (or $PSPACE$). Can you make a connection between this graph and Kleene star $L^{\ast}$?