Title :
On the complexity of learning with a small number of nodes
Author_Institution :
Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA
Abstract :
It is shown that the loading problem for a six-node neural network with a node function set AC10, 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 AC10 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
Keywords :
computational complexity; learning (artificial intelligence); neural nets; NP complete; NP hard; complexity of learning; loading problem; six-node neural network; three-input equality function; Boolean functions; Computer architecture; Computer networks; Concurrent computing; Distributed computing; Electronic mail; Neural networks; Page description languages;
Conference_Titel :
Neural Networks, 1992. IJCNN., International Joint Conference on
Conference_Location :
Baltimore, MD
Print_ISBN :
0-7803-0559-0
DOI :
10.1109/IJCNN.1992.227086
