KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №12, Moscow, 2003
Authors: Chashkin A.V.
On a method of computing partial Boolean functions
The article studies the average time of computation for values of a partial Boolean function with given weight by non-branching programs with a conditional stop operator. We suggest a new method for computing such functions, using consecutive approximations by partial functions that are in a sense simpler. New upper and lower bounds of the corresponding Shannon function are obtained that are of matching order. These bounds imply that the average computation time for almost all considered functions up to a constant multiple depends on the weight w of the computed function, does not depend on the size of the function domain, and equals θ(w/log2w).
complexity, Shannon function, Boolean function, partial function
Publication language: russian,  pages: 16 (p. 231-246)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Chashkin Aleksandr Viktorovich,  ,  механико-математический ф-т МГУ им. М.В.Ломоносова