Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:

Let $k \in \mathbb{N}$ and let $L \in \Sigma_k$. Show that also $L^{*} \in \Sigma_k$.

The following details from my lecture notes seem to be useful:

Notation. Let $n \in \mathbb{N}$.

We write $\exists_n y. \varphi(y)$ for $\exists y \in \Sigma^{*}.|y| \le n \wedge \varphi(y)$.

We write $\forall_n y. \varphi(y)$ for $\forall y \in \Sigma^{*}.|y| \le n \Rightarrow \varphi(y)$.


$L \in \Sigma^P_i \Leftrightarrow$ there is a language $A \in P$ and a polynomial $p$ so that: $x \in L \Leftrightarrow \exists_{p(|x|)}y_1 \forall_{p(|x|)}y_2 \exists_{p(|x|)}y_3 .../\forall_{p(|x|)}y_i (x,y_1,y_2,...,y_i) \in A$

Unfortunately I don't see the solution of the "puzzle". Can somebody please help me a little bit (despite the fact that it's weekend)?

share|cite|improve this question
up vote 4 down vote accepted

Let me assume your are familiar with the oracle-version of the polynomial hierarchy. Thus, if $L\in \Sigma_k$, then there exists a (non-deterministic polytime) Turing machine $M$ with oracle $\Sigma_{k-1}$.

To show that $L^*$ is also in $\Sigma_k$ we explain how one could build a new non-deterministic polytime Turing machine $M^*$ with oracle $\Sigma_{k-1}$ that accepts $L^*$. The key idea is, that we use the (simulation) of $M$ as a sub-module for $M^*$.

The machine $M^*$ works as follows. It guesses a partition of the input $w$ into some words $u_1u_2\cdots u_k$. Then it runs the simulation for $M$ for every $u_i$. If the simulation verifies that all $u_i\in L$ then $M^*$ accepts, otherwise it rejects. Clearly $M^*$ accepts $L^*$ and uses only the oracle $\Sigma_{k-1}$. What is left to check is if $M^*$ runs in polytime. The running time of $M^*$ is dominated by $$t_M(|u_1|)+t_M(|u_2|)+\cdots+ t_M(|u_k|)\le t_M(n)+t_M(n)+\cdots+ t_M(n)\le n \cdot t_M(n),$$ for $n=|w|$. Since $t_M(n)$ is a polynomial, we have that $n\cdot t_M(n)$ is a polynomial as well.

share|cite|improve this answer
Thank you very much for your answer, Professor Schulz. I unfortunately fail to understand why the oracle is $Σ_{k−1}$. Can you (or somebody else) please explain why the index has to be k-1? – Uriel Nov 24 '12 at 19:45
@Uriel: There are different (equivalent) ways how to define the classes in the polytime hierarchy. Please read the wikipedia article. One way to define $\Sigma_k$ is as the class NP with oracle $\Sigma_{k-1}$, where $\Sigma_0=P$. This definition was imho better suited for presenting a solution to your question. – A.Schulz Nov 25 '12 at 7:46
Thank you, now this is clear. I have a last question, which concerns the running time of $M^*$. The part $t_M(|u_1|)+t_M(|u_2|)+\cdots+ t_M(|u_k|)$ is clear. But why are there multiple $t_M(n)$? – Uriel Nov 25 '12 at 12:42
@Uriel: We have to show that the new machine runs in polytime. So we use as a very rough estimation $t_M(|u_i|)\le t_M(n)$ for each of the $t_M(|u_i|)$ terms. Also there are at most $n$ of such terms. – A.Schulz Nov 26 '12 at 20:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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