# 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? – Nicholas Mancuso Nov 25 '12 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? – Uriel Nov 26 '12 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.