Geodesic
On the complexity of recognizing a~set of vectors by a~neuron
Matematičeskie trudy, Tome 12 (2009) no. 1, pp. 130-143.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MT_2009_12_1_a4,
     author = {Yu. S. Okulovskii and V. Yu. Popov},
     title = {On the complexity of recognizing a~set of vectors by a~neuron},
     journal = {Matemati\v{c}eskie trudy},
     pages = {130--143},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2009_12_1_a4/}
}
TY  - JOUR
AU  - Yu. S. Okulovskii
AU  - V. Yu. Popov
TI  - On the complexity of recognizing a~set of vectors by a~neuron
JO  - Matematičeskie trudy
PY  - 2009
SP  - 130
EP  - 143
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2009_12_1_a4/
LA  - ru
ID  - MT_2009_12_1_a4
ER  - 
%0 Journal Article
%A Yu. S. Okulovskii
%A V. Yu. Popov
%T On the complexity of recognizing a~set of vectors by a~neuron
%J Matematičeskie trudy
%D 2009
%P 130-143
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2009_12_1_a4/
%G ru
%F MT_2009_12_1_a4
Yu. S. Okulovskii; V. Yu. Popov. On the complexity of recognizing a~set of vectors by a~neuron. Matematičeskie trudy, Tome 12 (2009) no. 1, pp. 130-143. http://geodesic.mathdoc.fr/item/MT_2009_12_1_a4/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] Okulovskii Yu. S., “O klassifikatsii lineino-razdelimykh funktsii”, Sb. nauch. tr. X Vserossiiskoi nauchno-tekhn. konf. “Neiroinformatika–2008”, Ch. 1, Izd-vo MIFI, M., 2008, 212–218

[3] Osovskii S., Neironnye seti dlya obrabotki informatsii, Finansy i statistika, M., 2002

[4] Khaikin S., Neironnye seti, Polnyi kurs, 2-e izd., Vilyams, M., 2006

[5] Khachiyan L. T., “Polinomialnyi algoritm v lineinom programmirovanii”, Dokl. AN SSSR, 244:5 (1979), 1093–1096 | MR | Zbl

[6] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968 | MR | Zbl

[7] Cover T. M., “Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition”, IEEE Trans. El. Computers, 14 (1965), 326–334 | DOI | Zbl

[8] Cover T. M., “The number of linearly induced orderings of points in $d$-space”, SIAM J. Appl. Math., 15:2 (1967), 434–439 | DOI | MR | Zbl

[9] Dobkin D. P., Reiss S. P., The Complexity of Linear Programming, Tech. Rep. 69, Dept. of Computer Science, Yale University, New Haven, 1976 | MR

[10] van Emde B. P., Another NP-Complete Problem and the Complexity of Computing Short Vectors in Lattice, Tech. Rep. 81-04, Matematische Institut, Amsterdam, 1981

[11] Frances M., Litman A., “On covering problem of codes”, Theory Comput. Syst., 30:2 (1997), 113–119 | MR | Zbl

[12] Hegedus T., Megiddo N., “On the geometric separability of Boolean functions”, Discrete Appl. Math., 66:3 (1996), 205–218 | DOI | MR

[13] Lanctot J. K., Li M., Ma B. et al., “Distinguishing string selection problems”, Proc. of the 10th Annual ACM-SIAM Symp. on Discrete Algorithms (Baltimore, MD, 1999), ACM, New York, 1999, 633–642 | MR | Zbl

[14] McCulloch W. S., Pitts W., “A logical calculus of the ideas immanent in nervous activity”, Bull. Math. Biophys., 5 (1943), 115–133 | DOI | MR | Zbl

[15] Minsky M., Papert S., Perceptrons, MIT Press, Cambridge, 1969 | Zbl

[16] Popov V. Yu., “Multiple genome rearrangement by swaps and by element duplications”, Theoret. Comput. Sci., 385:1–3 (2007), 115–126 | DOI | MR | Zbl

[17] Sima J., Opronen P., “Computational taxonomy and survey of neural networks models”, IEEE Trans. Neural Networks, 20:5 (2001), 50–61