# Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma_{0}^{p} & := P, \\ \Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}. \end{align}

Why is every language that is reducible to a language in $\Sigma_i^p$ also in $\Sigma_i^p$?

This comes in the proof of the theorem: If there is a PH-complete problem, then PH (the polynomial hierarchy) collapses.

First of all, there are many reduction concepts, but I assume you mean the polynomial reduction ($\le_p$).

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma_{0}^{p} & := P \\ \Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}} \end{align}

Let $A$ and $B$ be two languages over alphabets $\Sigma_A$ and $\Sigma_B$, respectively. Let $k \in \mathbb{N}_0$, $B \in \Sigma_{k}^{p}$ and $A \le_p B$. Since $A$ is polynomially reducible to $B$, there exists a function $f: \Sigma_A^\star \rightarrow \Sigma_B^\star$ (computable in polynomial time), such that $x \in A \Leftrightarrow f(x) \in B$. So we have an algorithm that decides $A$, which first transforms the input for $A$ to an input for $B$ using $f$, and then uses the algorithm for $B$ on the transformed instance. Therefore, $A$ is in $max\left\lbrace P, \Sigma_k^p \right\rbrace$.

If $k = 0$, $\Sigma_k^p = \Sigma_0^p = P$, then $A$ is also in $P = \Sigma_0^p$, since the transformation requires at most polynomial time and $B$ is in $P$.

If $k > 0$, the transformation is negligible and $A \in \Sigma_k^p$.

Let's take $\Sigma_3^p$ as an example. It is defined as the set of all languages of the form $$x \in L \Leftrightarrow \exists |y| < |x|^{c_1} \forall |z| < |x|^{c_2} \exists |w| < |x|^{c_3} \varphi(x,y,z,w),$$ where $\varphi$ is a polytime predicate. Here $\exists |y| < |x|^{c_1}$ means that there exists a string $y$ of length less than $|x|^{c_1}$ such that the bound formula holds.

Now suppose that a language $M$ is p-reducible to such a language $L$, say for some polytime $\psi$, $x \in M \Leftrightarrow \psi(x) \in L$. Suppose that $|\psi(x)| < |x|^d$. Then $$x \in M \Leftrightarrow \exists |y| < |x|^{dc_1} |y| < |\psi(x)|^{c_1} \land \forall |z| < |x|^{dc_2} |z| < |\psi(x)|^{c_2} \Rightarrow \exists |w| < |x|^{dc_3} |w| < |\psi(x)|^{c_3} \land \varphi(\psi(x),y,z,w).$$ Equivalently, $$x \in M \Leftrightarrow \exists |y| < |x|^{dc_1} \forall |z| < |x|^{dc_2} \exists |w| < |x|^{dc_3} |y| < |\psi(x)|^{c_1} \land ( |z| < |\psi(x)|^{c_2} \Rightarrow (|w| < |\psi(x)|^{c_3} \land \varphi(\psi(x),y,z,w))).$$ It's not hard to check that the new predicate is also polytime, and so $M \in \Sigma_3^p$.