Geodesic
Estimates for the complexity of a method for solving the problem of inclusive search
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 118-139

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

We suggest a method to solve the problem of inclusive search, which has three versions depending on the chosen base set: the set of monotone Boolean function, the set of elementary monotone conjunctions, and the set of Boolean variables. For each version, we estimate the Shannon function for the method complexity and the mean value of the complexity; we study the asymptotic behaviour of the Shannon function and of the logarithm of the mean value, and find that the Shannon function for the complexity of the method suggested asymptotically behaves as the Shannon function for the complexity of inclusive search. This research was supported by the Russian Foundation for Basic Research, grant 98–01–00130. 
@article{DM_2000_12_2_a9,
     author = {\`E. \`E. Gasanov},
     title = {Estimates for the complexity of a method for solving the problem of inclusive search},
     journal = {Diskretnaya Matematika},
     pages = {118--139},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2000},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/}
}
TY  - JOUR
AU  - È. È. Gasanov
TI  - Estimates for the complexity of a method for solving the problem of inclusive search
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 118
EP  - 139
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/
LA  - ru
ID  - DM_2000_12_2_a9
ER  - 
%0 Journal Article
%A È. È. Gasanov
%T Estimates for the complexity of a method for solving the problem of inclusive search
%J Diskretnaya Matematika
%D 2000
%P 118-139
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/
%G ru
%F DM_2000_12_2_a9
È. È. Gasanov. Estimates for the complexity of a method for solving the problem of inclusive search. Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 118-139. http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/