Geodesic
On the constructive characterization of threshold functions
Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 4, pp. 189-208.

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

In this paper, structure of the set of threshold functions and complexity problems are considered. The notion of a signature of threshold function is defined. It is shown that if threshold function essentially depends on all of its variables then signature of this function is unique. Set of threshold functions is partitioned onto classes with equal signatures. Theorem characterizing this partition is proved. Importance of the class of monotone threshold functions is emphasized. Complexity of transferring one threshold function specified by the linear form into another is examined. It is shown that in the worst case this transferring would take exponential time. Structure of the set of linear forms specifying the same threshold function is also examined. It is proved that for any threshold function this set of linear forms has unique basis in terms of the operation of addition of the linear forms. It is also shown that this basis is countable. 
@article{FPM_2009_15_4_a6,
     author = {A. P. Sokolov},
     title = {On the constructive characterization of threshold functions},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {189--208},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2009_15_4_a6/}
}
TY  - JOUR
AU  - A. P. Sokolov
TI  - On the constructive characterization of threshold functions
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2009
SP  - 189
EP  - 208
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2009_15_4_a6/
LA  - ru
ID  - FPM_2009_15_4_a6
ER  - 
%0 Journal Article
%A A. P. Sokolov
%T On the constructive characterization of threshold functions
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2009
%P 189-208
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2009_15_4_a6/
%G ru
%F FPM_2009_15_4_a6
A. P. Sokolov. On the constructive characterization of threshold functions. Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 4, pp. 189-208. http://geodesic.mathdoc.fr/item/FPM_2009_15_4_a6/

[1] Hastad J., “On the size of weights for threshold gates”, SIAM J. Discrete Math., 7 (1994), 484–492 | DOI | MR | Zbl