Geodesic
A lower bound for the complexity of information networks for a partial ordering relation
Diskretnaya Matematika, Tome 8 (1996) no. 4, pp. 108-122 
È. È. Gasanov. A lower bound for the complexity of information networks for a partial ordering relation. Diskretnaya Matematika, Tome 8 (1996) no. 4, pp. 108-122. http://geodesic.mathdoc.fr/item/DM_1996_8_4_a8/
@article{DM_1996_8_4_a8,
     author = {\`E. \`E. Gasanov},
     title = {A lower bound for the complexity of information networks for a partial ordering relation},
     journal = {Diskretnaya Matematika},
     pages = {108--122},
     year = {1996},
     volume = {8},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_4_a8/}
}
TY  - JOUR
AU  - È. È. Gasanov
TI  - A lower bound for the complexity of information networks for a partial ordering relation
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 108
EP  - 122
VL  - 8
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_4_a8/
LA  - ru
ID  - DM_1996_8_4_a8
ER  - 
%0 Journal Article
%A È. È. Gasanov
%T A lower bound for the complexity of information networks for a partial ordering relation
%J Diskretnaya Matematika
%D 1996
%P 108-122
%V 8
%N 4
%U http://geodesic.mathdoc.fr/item/DM_1996_8_4_a8/
%G ru
%F DM_1996_8_4_a8

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

We study the search problems where the search relation is a partial order relation. We reveal the common property of these problems called the existence of principal chains. Using this property, we obtain a lower bound for the complexity of the search problems with the natural partial order relation given on the Boolean cube, and prove that the lower bound is asymptotically attainable.This work was supported by the Russian Foundation for Basic Research, grant 95–01–00597.