FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2009, VOLUME 15, NUMBER 3, PAGES 135-181

On algorithm complexity

V. B. Kudryavtsev
A. E. Andreev

Abstract

View as HTML     View as gif image

This paper contains review of the authors' results in the theory of algorithm complexity. The results described concern the methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions), asymptotically optimal functional networks' synthesis, Boolean functions minimization, and the problems of solving Boolean equations.

Location: http://mech.math.msu.su/~fpm/eng/k09/k093/k09310h.htm
Last modified: January 13, 2010