Skip to main content
Computer Science

Return to Question

added 54 characters in body
Source Link
gradstudent
gradstudent
  • 493
  • 2
  • 8

Let me split my query into a few parts which possibly have overlapping answers,

  1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) are in $NP/poly$? (I saw this claimed in athe conclusion of this recent paper https://arxiv.org/abs/1705.02397 without any proof or reference.)

  2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?

  3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?

  4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT_3} \subseteq NP/poly$ when we know that $\hat{LT_3} \subseteq P/poly$? What am I missing?

Let me split my query into a few parts which possibly have overlapping answers,

  1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) are in $NP/poly$? (I saw this claimed in a recent paper without any proof or reference.)

  2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?

  3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?

  4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT_3} \subseteq NP/poly$ when we know that $\hat{LT_3} \subseteq P/poly$? What am I missing?

Let me split my query into a few parts which possibly have overlapping answers,

  1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) are in $NP/poly$? (I saw this claimed in the conclusion of this recent paper https://arxiv.org/abs/1705.02397 without any proof or reference.)

  2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?

  3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?

  4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT_3} \subseteq NP/poly$ when we know that $\hat{LT_3} \subseteq P/poly$? What am I missing?

Source Link
gradstudent
gradstudent
  • 493
  • 2
  • 8

Some questions about the depth hierarchy of threshold circuits

Let me split my query into a few parts which possibly have overlapping answers,

  1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) are in $NP/poly$? (I saw this claimed in a recent paper without any proof or reference.)

  2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?

  3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?

  4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT_3} \subseteq NP/poly$ when we know that $\hat{LT_3} \subseteq P/poly$? What am I missing?