3
$\begingroup$

When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a reduction that fulfills the following property: If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is also $\Sigma_i^P$ or $\Pi_i^P$.

I can see how Karp-reductions fulfill this requirement for the complexity class $P$. How could one proof that Karp-reduction fulfill this requirement for all other complexity classes in the polynomial hierachy?

$\endgroup$
3
$\begingroup$

Suppose that $f$ is the polynomial reduction between $L'$ and $L$, i.e. $x \in L' \Leftrightarrow f(x) \in L$. If $L \in \Sigma_k^p$ then $y\in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(y, z_1, \ldots z_k) = 1$. Then $$x\in L \Leftrightarrow f(x) \in L \Leftrightarrow \exists z_1 \forall z_2 \ldots M(f(x), z_1, \ldots z_k) = 1 \Leftrightarrow \exists z_1 \forall z_2 \ldots P(x, z_1, \ldots z_k) = 1$$ $P$ first computes $f$, then applies $M$, so it's polynomial.

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