<p>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:</p>

<ul>
<li>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</li>
<li>For the other direction, see the comments by Kaveh below.</li>
</ul>

CC BY-SA 3.0
2017-02-09T22:18:40.167Z
Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse?
Daniel Apon
CC BY-SA 3.0
2017-02-09T23:33:59.713Z
@Daniel, I think you can get rid of the quantifiers uniformity in the circuit, so yes, if PH collapses them so does nuPH.
Kaveh
CC BY-SA 3.0
2017-02-09T23:39:48.423Z
@Kaveh: How? I may be being slow, but I don't see it yet...
Joshua Grochow
CC BY-SA 3.0
2017-02-10T02:23:54.857Z
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
CC BY-SA 3.0
2017-02-10T04:48:41.243Z
Is the notation $\textsf{nuPH}$ used anywhere else? I am not very familiar with how computer scientists name things.
Danny Nguyen
CC BY-SA 3.0
2017-02-10T05:16:13.997Z
I made it up. (However, the notation $\mathsf{nuPPT}$ -- meaning "non-uniform probabilistic polynomial-time" -- has been used in a handful of theory of cryptography papers.. There's nothing particularly special about the notation; I mean what you mean. :-))
Daniel Apon
CC BY-SA 3.0
2017-02-10T13:08:10.340Z
PH/poly is certainly the standard notation. I’ve never seen the nu prefix.
Emil Jeřábek
CC BY-SA 3.0
2017-02-10T14:13:30.267Z
I think I have seen nu prefix before but don't recall where.
Kaveh
CC BY-SA 3.0
2017-02-10T14:30:09.120Z
Probably better to stick with $\mathsf{PH/poly}$ :D
Daniel Apon
CC BY-SA 3.0
2017-02-09T21:58:39.307Z
2017-02-10T14:46:19.557Z
2017-02-10T14:46:19.557Z
Joshua Grochow
<p>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.</p>

<p>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$. </p>

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

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

<cc.complexity-theory><complexity-classes><polynomial-hierarchy>
Non-uniform version for the whole polynomial hierarchy
Danny Nguyen
# Non-uniform version for the whole polynomial hierarchy

(Asked by: username_0 on 2017-02-09)

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?

**Tags:** cc.complexity-theory, complexity-classes, polynomial-hierarchy

---

## 1 answers

### Answer by username_1 on 2017-02-09. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse?  
> **username_3**: @Daniel, I think you can get rid of the quantifiers uniformity in the circuit, so yes, if PH collapses them so does nuPH.  
> **username_1**: @Kaveh: How? I may be being slow, but I don't see it yet...  
> **username_3**: 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.  
> **username_0**: Is the notation $\textsf{nuPH}$ used anywhere else? I am not very familiar with how computer scientists name things.  
> **username_2**: I made it up. (However, the notation $\mathsf{nuPPT}$ -- meaning "non-uniform probabilistic polynomial-time" -- has been used in a handful of theory of cryptography papers.. There's nothing particularly special about the notation; I mean what you mean. :-))  
> **username_4**: PH/poly is certainly the standard notation. I’ve never seen the nu prefix.  
> **username_3**: I think I have seen nu prefix before but don't recall where.  
> **username_2**: Probably better to stick with $\mathsf{PH/poly}$ :D  

---

