# Show that a language belongs to the polynomial hierarchy

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

Theorem.

$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)?

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.
• 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? Nov 24, 2012 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. Nov 25, 2012 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)$? Nov 25, 2012 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. Nov 26, 2012 at 20:11