<p>There are some references I could find: 
<a href="http://www.mitpressjournals.org/doi/abs/10.1162/089976603322518731" rel="noreferrer">General-purpose computation with neural networks: A survey of complexity theoretic results, 2003</a> and <a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=kVhZDTKYa8MC&amp;oi=fnd&amp;pg=PA469&amp;dq=the+computation+complexity+of+neural+networks+ac0&amp;ots=ibM6gABynC&amp;sig=ELw-AraHjjnzVWo5qdpdbAHGAUg" rel="noreferrer">Counting hierarchies: polynomial time and constant depth circuits, 1993</a>. </p>

<p>It appears that neural networks are considered threshold circuits; i.e. those circuits using MAJORITY gates. In <a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=kVhZDTKYa8MC&amp;oi=fnd&amp;pg=PA469&amp;dq=the+computation+complexity+of+neural+networks+ac0&amp;ots=ibM6gABynC&amp;sig=ELw-AraHjjnzVWo5qdpdbAHGAUg" rel="noreferrer">(2)</a> it is the case that a depth $d$ neural network has complexity $TC^0_d$ (here's a link to <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tc0" rel="noreferrer">link</a> to complexity zoo entry about $TC^0$). </p>

<p>Since $TC^0$ containts $ACC^0$, which is $AC^0$ with arbitrary MOD gates, then $AC^0 \subset TC^0$. Also, it is mentioned in the zoo that such circuits with depth 3 are strictly more powerful than those of depth 2.</p>

<p>In <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1991.185447" rel="noreferrer">On the computational power of sigmoid versus Boolean threshold circuits,1991</a> it is mentioned that for a constant depth $d$, Boolean and real-valued threshold circuits (with polynomially bounded weights) are essentially the same.</p>

CC BY-SA 2.5
2010-11-04T05:34:09.570Z
Interesting, thanks. This is what I was looking for. More interesting still is that $TC^0$ has a complete problems ... hmm ...
gabgoh
CC BY-SA 3.0
2010-11-04T05:20:00.867Z
2014-04-17T22:49:38.370Z
2014-04-17T22:49:38.370Z
Mohammad Alaggan
<p>Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from  $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to see that this has at least the same computational power as $AC^0$. Just for fun, we'll call the set of functions computable by a single layer neural network "$Neural$".</p>

<p>It seems, however, that it might have more computational power than $AC^0$ alone.</p>

<p>So ... is $AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?</p>

CC BY-SA 2.5
2010-11-04T18:33:31.370Z
A note on terminology -- important information is how many *hidden* layers there are. Zero hidden layer neural network with one output is just a linear threshold function, and is often (confusingly) called one layer or two layer neural network/perceptron, depending on whether inputs/outputs are considered layers. Also, in AI literature, neural networks are typically defined in terms of sigmoid functions which means that input/outputs are real valued. One hidden layer networks are known to be universal approximators in a sense that any continuous function can be approximated arbitrarily close
Yaroslav Bulatov
<cc.complexity-theory><circuit-complexity><machine-learning><ne.neural-evol>
Computational Power of Neural Networks?
gabgoh
# Computational Power of Neural Networks?

(Asked by: username_0 on 2010-11-04)

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to see that this has at least the same computational power as $AC^0$. Just for fun, we'll call the set of functions computable by a single layer neural network "$Neural$".

It seems, however, that it might have more computational power than $AC^0$ alone.

So ... is $AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

**Tags:** cc.complexity-theory, circuit-complexity, machine-learning, ne.neural-evol

> **Comments:**
> **username_1**: A note on terminology -- important information is how many *hidden* layers there are. Zero hidden layer neural network with one output is just a linear threshold function, and is often (confusingly) called one layer or two layer neural network/perceptron, depending on whether inputs/outputs are considered layers. Also, in AI literature, neural networks are typically defined in terms of sigmoid functions which means that input/outputs are real valued. One hidden layer networks are known to be universal approximators in a sense that any continuous function can be approximated arbitrarily close  

---

## 1 answers

### Answer by username_2 on 2010-11-04. Score: 17 | Accepted answer

There are some references I could find:
[General-purpose computation with neural networks: A survey of complexity theoretic results, 2003](http://www.mitpressjournals.org/doi/abs/10.1162/089976603322518731) and [Counting hierarchies: polynomial time and constant depth circuits, 1993](http://books.google.com/books?hl=en&lr=&id=kVhZDTKYa8MC&oi=fnd&pg=PA469&dq=the+computation+complexity+of+neural+networks+ac0&ots=ibM6gABynC&sig=ELw-AraHjjnzVWo5qdpdbAHGAUg).

It appears that neural networks are considered threshold circuits; i.e. those circuits using MAJORITY gates. In [(2)](http://books.google.com/books?hl=en&lr=&id=kVhZDTKYa8MC&oi=fnd&pg=PA469&dq=the+computation+complexity+of+neural+networks+ac0&ots=ibM6gABynC&sig=ELw-AraHjjnzVWo5qdpdbAHGAUg) it is the case that a depth $d$ neural network has complexity $TC^0\_d$ (here's a link to [link](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aT#tc0) to complexity zoo entry about $TC^0$).

Since $TC^0$ containts $ACC^0$, which is $AC^0$ with arbitrary MOD gates, then $AC^0 \subset TC^0$. Also, it is mentioned in the zoo that such circuits with depth 3 are strictly more powerful than those of depth 2.

In [On the computational power of sigmoid versus Boolean threshold circuits,1991](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1991.185447) it is mentioned that for a constant depth $d$, Boolean and real-valued threshold circuits (with polynomially bounded weights) are essentially the same.

> **Comments:**
> **username_0**: Interesting, thanks. This is what I was looking for. More interesting still is that $TC^0$ has a complete problems ... hmm ...  

---

