The article is a review of results in some areas of studying Boolean function complexity realized by branching programs. We define contact-rectifier circuits, the oriented and acyclic contact-rectifier circuits as control system models that are most similar to branching programs and define the non- determinstic and deterministic branching programs as well as complexity measures for these classes of circuits. A series of relations for these complexity measures is given for both non-deterministic and deterministic programs respectively. We consider branching programs of limited width and also read-k- times branching programs for obtaining lower bounds on complexity of branching programs without restrictions. The review was prepared based on the talks the author gave at the Control system synthesis workshop that took place in 1998 at NNSU and NII PMK in Nizhny Novgorod and the talks at the Young scientists workshops that were part of the 'Integration' program at MSU (Moscow, 1997) and NNSU (Nizhny Novgorod, 1998).

branching programs, Boolean function complexity, rectifier circuits, complexity lower bounds

Mathematical problems and theory of numerical methods