Skip to main content
Theoretical Computer Science

Return to Question

edited tags
Link
András Salamon
András Salamon
  • 19.2k
  • 3
  • 65
  • 151
edited body
Source Link
gabgoh
gabgoh
  • 1.5k
  • 12
  • 22

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 $Neural \subseteq AC^0$$AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

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 $Neural \subseteq AC^0$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

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?

added 20 characters in body
Source Link
gabgoh
gabgoh
  • 1.5k
  • 12
  • 22

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\{ 0,1\} ^{n}\rightarrow\{ 0,1\} $$\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 $Neural \subseteq AC^0$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\{ 0,1\} ^{n}\rightarrow\{ 0,1\} $, 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 $Neural \subseteq AC^0$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

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 $Neural \subseteq AC^0$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?

Source Link
gabgoh
gabgoh
  • 1.5k
  • 12
  • 22