Show that a language belongs to the polynomial hierarchy

Question

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

Answer 1

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.