2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Nicholas Mancuso Nov 25 '12 at 23:58
  • $\begingroup$ @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? $\endgroup$ – Uriel Nov 26 '12 at 17:16
1
$\begingroup$

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

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

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.