Geodesic
On the complexity and depth of circuits realizing partial Boolean functions
Diskretnaya Matematika, Tome 9 (1997) no. 2, pp. 53-58

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

The complexity and depth of circuits that realize partial Boolean functions are studied under the assumption that $FP\neq NC$. It is established that there exist partial Boolean functions for which the complexity and depth of circuits cannot be simultaneously close to the minimally possible values, i.e., any circuit realizing such a function has either a depth or a complexity that considerably exceeds either the depth or the complexity of the function which it realizes. 
@article{DM_1997_9_2_a4,
     author = {A. V. Chashkin},
     title = {On the complexity and depth of circuits realizing partial {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {53--58},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {1997},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1997_9_2_a4/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On the complexity and depth of circuits realizing partial Boolean functions
JO  - Diskretnaya Matematika
PY  - 1997
SP  - 53
EP  - 58
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1997_9_2_a4/
LA  - ru
ID  - DM_1997_9_2_a4
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On the complexity and depth of circuits realizing partial Boolean functions
%J Diskretnaya Matematika
%D 1997
%P 53-58
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1997_9_2_a4/
%G ru
%F DM_1997_9_2_a4
A. V. Chashkin. On the complexity and depth of circuits realizing partial Boolean functions. Diskretnaya Matematika, Tome 9 (1997) no. 2, pp. 53-58. http://geodesic.mathdoc.fr/item/DM_1997_9_2_a4/