# Non-uniform version for the whole polynomial hierarchy

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?

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.
• Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse? Commented Feb 9, 2017 at 22:18
• @Daniel, I think you can get rid of the quantifiers uniformity in the circuit, so yes, if PH collapses them so does nuPH. Commented Feb 9, 2017 at 23:33
• @Kaveh: How? I may be being slow, but I don't see it yet... Commented Feb 9, 2017 at 23:39
• 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. Commented Feb 10, 2017 at 2:23
• Probably better to stick with $\mathsf{PH/poly}$ :D Commented Feb 10, 2017 at 14:30