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


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.

  • $\begingroup$ 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? $\endgroup$ – Uriel Nov 24 '12 at 19:45
  • 1
    $\begingroup$ @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. $\endgroup$ – A.Schulz Nov 25 '12 at 7:46
  • $\begingroup$ 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)$? $\endgroup$ – Uriel Nov 25 '12 at 12:42
  • 1
    $\begingroup$ @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. $\endgroup$ – A.Schulz Nov 26 '12 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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