On the complexity of learning with a small number of nodes

It is shown that the loading problem for a six-node neural network with a node function set AC₁₀, i.e., the conjunction or disjunction of a subset of the inputs or their complements is NP complete. It can be deduced from this observation that the loading problem for a six-node analog neural network is NP hard. The loading problem for a four-node neural network with a node function set equal to AC₁₀ plus the three-input equality function is shown to be NP complete, and it is indicated how the required results can be derived in a similar fashion. Three loading problems are studied