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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Please don't delete your question after you've already received an answer. That is impolite to the person who took the time to write an answer. Part of our mission is to build up an archive of high-quality questions and answers that will help not only you but possibly others in the future as well. When people write an answer, they might be counting on the potential for others to benefit as well. $\endgroup$– D.W. ♦Apr 19, 2017 at 22:09
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/71895/755, math.stackexchange.com/q/2197148/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$– D.W. ♦Apr 19, 2017 at 22:10
-
$\begingroup$ @D.W. The version on Math.SE has an accepted answer. May be you should migrate this later version over there so that we can merge? I agree with you that crossposting is a common enough problem on our two sites. It is a problem only when the question is on-topic on both. I have only been a moderator fora bit over 2 years, so I don't know if there is an old meta-deal (or a network wide policy). $\endgroup$– Jyrki LahtonenApr 25, 2017 at 7:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Suppose you are given a language $L$ in one of these complexity classes, and you want to decide $L^*$ in the same complexity class. On input $x_1 \ldots x_n$ (where the $x_i$ are bits), use dynamic programming to find out which substrings $x_i x_{i+1} \ldots x_j$ belong to $L^*$. Since there are only $O(n^2)$ such substrings, this will only cause a polynomial blow-up in the resources used.
answered Mar 22, 2017 at 18:23
-
$\begingroup$ Wait, on input I have any word: $w$. My task is to decide in polynomial time and memory if there is such partition of $w=w_1..w_n$ that $w_i\in L$ for each $i=1...n$. You wrote on input $x_1...x_n$, what did you mean ? Input is $x$, the aim is to find parition. (Checking all paritions requires exponential time, about memory it is difficult to say) $\endgroup$– user54001Mar 22, 2017 at 19:01
-
$\begingroup$ The $x_i$ are bits, not words in $L$. $\endgroup$ Mar 22, 2017 at 19:25
-
$\begingroup$ I don't understand your solution. I understand what we should show and I can see where are you going. However, why it that $x_i$ are bits matter ? For me, $x_i$ may be symbol from alphabet. Secondly, you wrote belong to $L*$. How do you check if belong to $L^*$ ? After all we must construct this machine, not use it. $\endgroup$– user54001Mar 22, 2017 at 19:38
-
$\begingroup$ @HaskellFun You use dynamic programming. Unfortunately I'm not willing to offer any more help. $\endgroup$ Mar 22, 2017 at 19:40
-
$\begingroup$ Thridly, did your algorithm check in $O(n^2) $ each possible partition ? $\endgroup$– user54001Mar 22, 2017 at 19:40