Geodesic
On the complexity of the disjunctive normal form of threshold functions
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 85-92 
O. V. Shabanin. On the complexity of the disjunctive normal form of threshold functions. Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 85-92. http://geodesic.mathdoc.fr/item/DM_2000_12_2_a5/
@article{DM_2000_12_2_a5,
     author = {O. V. Shabanin},
     title = {On the complexity of the disjunctive normal form of threshold functions},
     journal = {Diskretnaya Matematika},
     pages = {85--92},
     year = {2000},
     volume = {12},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_2_a5/}
}
TY  - JOUR
AU  - O. V. Shabanin
TI  - On the complexity of the disjunctive normal form of threshold functions
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 85
EP  - 92
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_2_a5/
LA  - ru
ID  - DM_2000_12_2_a5
ER  - 
%0 Journal Article
%A O. V. Shabanin
%T On the complexity of the disjunctive normal form of threshold functions
%J Diskretnaya Matematika
%D 2000
%P 85-92
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a5/
%G ru
%F DM_2000_12_2_a5

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

We consider the problem on estimating the complexity of the disjunctive normal form (d.n.f.) of threshold functions in $n$ variables, where the complexity is the minimal number of simple implicants in the representation of the d.n.f. It is known that the complexity of the d.n.f. of almost all threshold functions is no less than $n^2/\log_2 n$. We prove inequalities, which connect the complexity $L \nu(f)$ of the d.n.f. of a threshold function $f$ with the Chow parameters. By using these inequalities we show that for almost all threshold functions, for sufficiently large $n$, $$ \log_2 L\nu(f)>n-2\sqrt{2n\log_2 n}(1+\delta(n)), $$ where $\delta(n)$ is an arbitrary function such that $\delta(n)\to 0$ and $n\delta(n)\to \infty$ as $n\to\infty$.

[1] Butakov E. A., Metody sinteza releinykh ustroistv iz porogovykh elementov, Energiya, Moskva, 1970

[2] Dertouzos M., Porogovaya logika, Mir, Moskva, 1967

[3] Zuev Yu. A., “Porogovye funktsii i porogovye predstavleniya bulevykh funktsii”, Matematicheskie voprosy kibernetiki, 5 (1994), 5–61 | MR | Zbl

[4] Zuev Yu. A., Lipkin L. I., “Regulyarnye bulevy funktsii s zadannoi slozhnostyu doz'yunktivnykh normalnykh form”, Metody diskretnogo analiza v izuchenii bulevykh funktsii i grafov, 48 (1989), 17–22, IM SO AN SSSR, Novosibirsk | MR

[5] Zuev Yu. A., “Asimptotika logarifma chisla porogovykh funktsii algebry logiki”, Dokl. AN SSSR, 306:3 (1989), 528–530 | MR | Zbl

[6] Muroga S., Threshold Logic and its Applications, Wiley, New York, 1971 | MR | Zbl

[7] Nigmatullin R. G., Slozhnost bulevykh funktsii, Nauka, Moskva, 1990 | MR

[8] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1979 | MR | Zbl

[9] Yablonskii S. V., Diskretnaya matematika i matematicheskaya kibernetika, Nauka, Moskva, 1974