(I am hugely editing the question. My initial question was if lowerbounds on threshold circuits say anything about P/NP and it seems that they dont. Irrespective of P/NP its an independently true fact that there exists Boolean functions which are exponentially hard for threshold circuits just that we have never seen them.)

Let me ask my followup question in $3$ parts which I guess are related,

  1. If one looks at the space of all polynomial sized threshold circuits (at constant depth or not) then do we know of any natural complexity class in which they sit? The closest I know of is that the class of depth 3 threshold circuits with no weight restriction are known to be in $NP/poly$. What happens at higher or non-constant depths?

  2. Is there any class of circuits against which we know that there cannot be exponentially hard functions if $P=NP$? (Threshold circuits are clearly not of this type.)

  3. Are there reasons to believe that for each depth $d$ there exists a Boolean function which is easy for depth $d+1$ but exponentially hard for depth $d$? And if such functions are found then would it have any implications (separations) for the other usual complexity classes?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/P/poly ​ ​ $\endgroup$ – user6973 Oct 4 '17 at 23:29
  • $\begingroup$ Could you kindly elaborate on the connection between P/poly and my question? $\endgroup$ – gradstudent Oct 5 '17 at 1:32
  • $\begingroup$ "representable in polynomial size by" circuits "with any combination of gates such that each gate is a polynomial time computable function" ​ simplifies to ​ "in P/poly" . ​ ​ ​ ​ $\endgroup$ – user6973 Oct 5 '17 at 1:41
  • $\begingroup$ So is any kind of threshold circuit (with or without weight restriction on a subset of the layers) known to be in P/poly? Or how does this help answer my first 2 questions? (..the closest thing to your comment that I am aware of is that depth $3$ threshold circuits with polynomially bounded integral weights is the largest threshold circuit class known to be contained inside $NP/poly$...) $\endgroup$ – gradstudent Oct 5 '17 at 1:48
  • 2
    $\begingroup$ Polynomial-size circuits with arbitrary threshold gates can be computed by polynomial-size circuits over De Morgan basis. $\endgroup$ – Emil Jeřábek Oct 5 '17 at 6:40

In the same paper that shows the $n^{1.5}$ lower bound for depth-2 (Daniel Kane and me) we also show that a random function is extremely likely to have depth 2 threshold circuit complexity at least $$2^n/n^3$$.

So the answer to question 2 is "yes"

Since random functions need large threshold circuits, question 1 seems to be effectively asking "does $P \neq NP$ imply TRUE" so the answer should also be "yes", since both TRUE and FALSE imply TRUE.

| cite | improve this answer | |
  • $\begingroup$ Thanks! I guess I am not understanding how your paper's argument answers my question 1. In my question 1 I am not constraining the depth of the LTF or PTF circuit to be 2 as is required for your argument above. Maybe those functions which are exponentially hard for depth 2 LTFs become polynomial sized for higher depth LTFs? (..also my separate question below the dotted line was as to what is the largest/strongest basis of gates over which one expects exponential size lower bounds if $P \neq NP$ - can this basis include LTF/PTFs with or without some weight restriction..) $\endgroup$ – gradstudent Oct 5 '17 at 5:27
  • 2
    $\begingroup$ There are at most $2^{k^2}$ linear threshold functions on $k$ variables. Thus a Shannon-style counting lower bound shows that there exists a Boolean function on $n$ variables requiring threshold circuits of size $2^{\Omega(n)}$ regardless of the depth. $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 5 '17 at 7:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.