Body: <p>Suppose I have a Boolean function that maps <span class="math-container">$N$</span> bits to <span class="math-container">$1$</span> bit. If I understand correctly, this function will have <span class="math-container">$2^{2^N}$</span> possible configurations of its truth table.</p>
  <p>What is the minimum number of neurons and hidden layers I would need in order to have a multi-layer perceptron capable of learning all possible truth tables?</p>
  <p>I found one set of lecture notes <a href="http://deeplearning.cs.cmu.edu/slides/lec2.universal.pdf" rel="nofollow noreferrer">here</a> that suggests that &quot;checkerboard&quot; shaped truth tables (which is something like an N-input XOR function) are hard to learn, but do they represent the worst-case scenario? The notes suggest that such tables require <span class="math-container">$3\cdot(N-1)$</span> neurons arranged in <span class="math-container">$2 \cdot\log_2(N$</span>) hidden layers</p>
  
Tags: <computational-learning-theory><multilayer-perceptrons><artificial-neuron><hidden-layers><capacity>
Title: What is the minimum number of neurons and hidden layers needed to learn a Boolean function that maps $N$ bits to $1$ bit?
UserDisplayName: wil3
ThreadText: # What is the minimum number of neurons and hidden layers needed to learn a Boolean function that maps $N$ bits to $1$ bit?
  
  (Asked by: username_0 on 2018-04-12)
  
  Suppose I have a Boolean function that maps $N$ bits to $1$ bit. If I understand correctly, this function will have $2^{2^N}$ possible configurations of its truth table.
  
  What is the minimum number of neurons and hidden layers I would need in order to have a multi-layer perceptron capable of learning all possible truth tables?
  
  I found one set of lecture notes [here](http://deeplearning.cs.cmu.edu/slides/lec2.universal.pdf) that suggests that "checkerboard" shaped truth tables (which is something like an N-input XOR function) are hard to learn, but do they represent the worst-case scenario? The notes suggest that such tables require $3\cdot(N-1)$ neurons arranged in $2 \cdot\log\_2(N$) hidden layers
  
  **Tags:** computational-learning-theory, multilayer-perceptrons, artificial-neuron, hidden-layers, capacity
  
  ---
  
  ## 0 answers
  
  