Abstract:
The method of obtaining lower bounds on the complexity of Boolean functions for nondeterministic branching programs is proposed. A nonlinear lower bound on the complexity of characteristic functions of Reed--Muller codes for nondeterministic branching programs is obtained.