The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly. Similarly, we can define a non-uniform version for each level in the PH.

For example: $\Sigma_2$/poly consists of problems of the form $\{x : \exists y \forall z \; C(x,y,z)\}$, where C is a circuit of polynomial size that may vary depending on the length of the input string $x$, and $y,z$ also have lengths polynomial in $x$.

Doing this for all levels of PH, we get a non-uniform version PH/poly.

QUESTIONS: Is there anything known about this hierarchy? Does it collapse? Or is there another name for it in the literature?


1 Answer 1


Well, sure, we know things. I think this is a pretty standard nomenclature for it. This hierarchy collapses if and only if $\mathsf{PH}$ does, exercise:

  • For one direction, modify the proof of Karp-Lipton to show that if $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ then $\mathsf{PH}$ collapses, and observe that this result relativizes
  • For the other direction, see the comments by Kaveh below.
  • 1
    $\begingroup$ Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse? $\endgroup$ Commented Feb 9, 2017 at 22:18
  • 1
    $\begingroup$ @Daniel, I think you can get rid of the quantifiers uniformity in the circuit, so yes, if PH collapses them so does nuPH. $\endgroup$
    – Kaveh
    Commented Feb 9, 2017 at 23:33
  • 2
    $\begingroup$ @Kaveh: How? I may be being slow, but I don't see it yet... $\endgroup$ Commented Feb 9, 2017 at 23:39
  • 4
    $\begingroup$ Assume P=NP. Consider L in PH/poly. Let's assume L $\in$ $\Sigma^P_k$/poly, that is $\chi_L(x) = \chi_{L'}(x,f(|x|))$ for some advice function f $\in$ poly and L' is in $\Sigma^P_k$. But L' is in P, therefore L is in P/poly. $\endgroup$
    – Kaveh
    Commented Feb 10, 2017 at 2:23
  • 3
    $\begingroup$ Probably better to stick with $\mathsf{PH/poly}$ :D $\endgroup$ Commented Feb 10, 2017 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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