# 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
• Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse? – Daniel Apon Feb 9 '17 at 22:18
• 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. – Kaveh Feb 10 '17 at 2:23
• Probably better to stick with $\mathsf{PH/poly}$ :D – Daniel Apon Feb 10 '17 at 14:30