Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
Thank you very much, Nicholas. Now everything is clear to me. – Uriel Nov 26 '12 at 18:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.