On the complexity of recognizing a set of vectors by a neuron

Yu. S. Okulovskii, V. Yu. Popov

Department of Mathematics and Mechanics (Chair of Algebra and Discrete Mathematics) Ural State University, Ekaterinburg, Russia

Abstract: We consider the problems connected with the computational abilities of a neuron. The orderings of finite subsets of real vectors associated with neural computing are studied. We construct a lattice of such orderings and study some its properties. The interrelation between the orders on the sets and the neuron implementation of functions defined on these sets is derived. We prove the NP-hardness of “The Shortest Vector” problem and represent the relationship of the problem with neural computing.

Key words: neural networks, discrete functions, computational capability, computational complexity.

UDC: 519.7

Received: 29.08.2008

 English version: Siberian Advances in Mathematics, 2010, 20:4, 293–300

Bibliographic databases:

•