Geodesic
Complexity and structure of circuits for parity functions
Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 6, pp. 147-153 
Yu. A. Kombarov. Complexity and structure of circuits for parity functions. Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 6, pp. 147-153. http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a5/
@article{FPM_2015_20_6_a5,
     author = {Yu. A. Kombarov},
     title = {Complexity and structure of circuits for parity functions},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {147--153},
     year = {2015},
     volume = {20},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a5/}
}
TY  - JOUR
AU  - Yu. A. Kombarov
TI  - Complexity and structure of circuits for parity functions
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2015
SP  - 147
EP  - 153
VL  - 20
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a5/
LA  - ru
ID  - FPM_2015_20_6_a5
ER  - 
%0 Journal Article
%A Yu. A. Kombarov
%T Complexity and structure of circuits for parity functions
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2015
%P 147-153
%V 20
%N 6
%U http://geodesic.mathdoc.fr/item/FPM_2015_20_6_a5/
%G ru
%F FPM_2015_20_6_a5

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

The paper is devoted to circuits implementing parity functions. A review of results establishing exact values of the complexity of parity functions is given. The structure of optimal circuits implementing parity functions is described for some bases. For one infinite basis, an upper bound for the complexity of parity functions is given.

[1] Kombarov Yu. A., “O minimalnykh realizatsiyakh lineinykh bulevykh funktsii”, Diskret. analiz i issled. operatsii, 19:3 (2012), 39–57 | MR | Zbl

[2] Kombarov Yu. A., “O minimalnykh skhemakh v bazise Sheffera dlya lineinykh bulevykh funktsii”, Diskret. analiz i issled. operatsii, 20:4 (2013), 65–87 | MR | Zbl

[3] Redkin N. P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23 (1970), 83–101 | Zbl

[4] Redkin N. P., “O minimalnoi realizatsii lineinoi funktsii skhemoi iz funktsionalnykh elementov”, Kibernetika, 6 (1971), 31–38 | Zbl

[5] Shkrebela I. S., “O slozhnosti realizatsii lineinykh bulevykh funktsii skhemami iz funktsionalnykh elementov v bazise $\{x \to y,\, \overline{x}\}$”, Diskret. matem., 15:4 (2003), 100–112 | DOI | MR | Zbl

[6] Lai H. Ch., Muroga S., “Logic networks with a minimum number of NOR (NAND) gates for parity functions of $n$ variables”, IEEE Trans. Comput., C-36:2 (1987), 157–166

[7] Podolskaya O., On circuit complexity of parity and majority functions in antichain basis, arXiv: 1410.2456 [cs.CC]

[8] Wegner I., “The complexity of the parity function in unbounded fan-in, unbounded depth circuits”, Theor. Comput. Sci., 85 (1991), 155–170 | DOI | MR