8
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.
Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Can $\mathsf{PH}$ collapse but $\mathsf{nuPH}$ not collapse? $\endgroup$
    – Daniel Apon
    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
    Feb 9, 2017 at 23:33
  • 2
    $\begingroup$ @Kaveh: How? I may be being slow, but I don't see it yet... $\endgroup$
    – Joshua Grochow
    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
    Feb 10, 2017 at 2:23
  • 3
    $\begingroup$ Probably better to stick with $\mathsf{PH/poly}$ :D $\endgroup$
    – Daniel Apon
    Feb 10, 2017 at 14:30

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.