# Strict polynomial hierarchy and reduction

The following exercise gives me headaches:

Show: If the polynomial hierarchy is strict (i.e. $\forall k \in \mathbb{N}. \Sigma_k \neq \Sigma_{k+1}$), then there is no $\text{PH}$-complete problem for polynomial-time reductions (i.e. there is no problem $\text{P} \in \text{PH}$ such that each problem in $\text{PH}$ can be reduced to $\text{P}$ through a function $f \in \text{FP}$).

The exercise describes in detail what has to be shown, but my issue is that I don't know how to show this. Can somebody please help me?

• HINT: If there did exist a PH-Complete problem, what level would it reside in (ie, what $\Sigma_i$) and what does that mean as far as collapses go? Nov 25, 2012 at 23:58
• @Nicholas: I think it would reside in that $\Sigma_i$ with a very high $i$ and then $\text{PH}=\Sigma_i$. Intuitively it is clear to me what the exercise says. The only problem is how to prove this. Can you give me some further help, please? Nov 26, 2012 at 17:16

$\newcommand{\PH}{\mathsf{PH}}$To expand the comments:
Suppose there did exist a $\PH$-Complete language $L \in \Sigma_i$ for some $i$. By definition of completeness $L' \leq L$ for all $L' \in \PH$. Therefore there exists some language $L' \in \Sigma_{i+1}$ that reduces to $L$. This is a contradiction with the strictness assumption. Indeed, we conclude that no such $\PH$-Complete language exists.