1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.