On the realization of linear Boolean operators by nonbranching programs with a conditional stop

The complexity of the realization of linear Boolean operators by straight-line programs with a conditional stop is considered. Exact, in order of magnitude, bounds on the average execution time of almost all such operators are found.
This research was supported by the Russian Foundation for Basic Research, grant 96–01–01068, and the Federal Program ‘Integration’, grant 473.