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

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


Diskr. Mat., 2006, Volume 18, Issue 2, Pages 71–83 (Mi dm47)  

This article is cited in 1 scientific paper (total in 1 paper)

On the mean complexity of monotone functions

R. N. Zabaluev


Abstract: We consider the complexity of realisation of the monotone functions by straight-line programs with conditional stop. It is shown that the mean complexity of each monotone function of $n$ variables does not exceed $a{2^n}/{n^{2}}(1+o(1))$ as $n\to\infty$, and the mean complexity of almost all monotone functions of $n$ variables is at least $b{2^n}/{n^{2}}(1+o(1))$ as $n\to\infty$, where $a$ and $b$ are constants.
This research was supported by the Russian Foundation for Basic Research, grant 05–01–0099, by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1807.2003.1, by the Program ‘Universities of Russia,’ grant 04.02.528, and by the Program of Fundamental Research of the Department of Mathematical Sciences of the Russian Academy of Sciences ‘Algebraic and Combinatorial Methods of Mathematical Cybernetics,’ project ‘Optimal synthesis of control circuits.’

DOI: https://doi.org/10.4213/dm47

Full text: PDF file (1199 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2006, 16:2, 181–194

Bibliographic databases:

UDC: 519.7
Received: 12.05.2005

Citation: R. N. Zabaluev, “On the mean complexity of monotone functions”, Diskr. Mat., 18:2 (2006), 71–83; Discrete Math. Appl., 16:2 (2006), 181–194

Citation in format AMSBIB
\Bibitem{Zab06}
\by R.~N.~Zabaluev
\paper On the mean complexity of monotone functions
\jour Diskr. Mat.
\yr 2006
\vol 18
\issue 2
\pages 71--83
\mathnet{http://mi.mathnet.ru/dm47}
\crossref{https://doi.org/10.4213/dm47}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2283332}
\zmath{https://zbmath.org/?q=an:1145.94029}
\elib{http://elibrary.ru/item.asp?id=9311196}
\transl
\jour Discrete Math. Appl.
\yr 2006
\vol 16
\issue 2
\pages 181--194
\crossref{https://doi.org/10.1515/156939206777344629}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33746055746}


Linking options:
  • http://mi.mathnet.ru/eng/dm47
  • https://doi.org/10.4213/dm47
  • http://mi.mathnet.ru/eng/dm/v18/i2/p71

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Chashkin, “Bounds for the average-case complexity of monotone Boolean functions”, Discrete Math. Appl., 27:3 (2017), 137–142  mathnet  crossref  crossref  mathscinet  isi  elib
  • Дискретная математика
    Number of views:
    This page:341
    Full text:152
    References:27
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020