Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Diskretnaya Matematika, 2000, Volume 12, Issue 2, Pages 118–139
DOI: https://doi.org/10.4213/dm329 (Mi dm329) 		 
This article is cited in 1 scientific paper (total in 1 paper)

Estimates for the complexity of a method for solving the problem of inclusive search

È. È. Gasanov
Full-text PDF (1957 kB) Citations (1)
References:
PDF
HTML
DOI: https://doi.org/10.4213/dm329
Abstract: 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.
Received: 13.09.1999
Revised: 10.04.2000
Bibliographic databases:
UDC: 519.7
Language: Russian
Citation: È. È. Gasanov, “Estimates for the complexity of a method for solving the problem of inclusive search”, Diskr. Mat., 12:2 (2000), 118–139; Discrete Math. Appl., 10:3 (2000), 295–318
Citation in format AMSBIB
\Bibitem{Gas00}
\by \`E.~\`E.~Gasanov
\paper Estimates for the complexity of a method for solving the problem of inclusive search
\jour Diskr. Mat.
\yr 2000
\vol 12
\issue 2
\pages 118--139
\mathnet{http://mi.mathnet.ru/dm329}
\crossref{https://doi.org/10.4213/dm329}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1783080}
\zmath{https://zbmath.org/?q=an:0969.68051}
\transl
\jour Discrete Math. Appl.
\yr 2000
\vol 10
\issue 3
\pages 295--318
Linking options:
  • https://www.mathnet.ru/eng/dm329
  • https://doi.org/10.4213/dm329
  • https://www.mathnet.ru/eng/dm/v12/i2/p118
    • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретная математика
    Statistics & downloads:
    Abstract page:400
    Full-text PDF :189
    References:38
    First page:1
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024