We consider circuits of functional elements of a finite depth whose elements arearbitrary Boolean functions of any number of arguments. We suggest a method of findingnonlinear lower bounds for complexity applicable, in particular, to the operator of cyclic convo-lution. The obtained lower bounds for the circuits of depth d ≥ 2 are of the form Ω (nλ_(d_1)(n)).In particular, for d = 2, 3, 4 they are of the form Ω(n~(3/2)),Ω(n logn),and nlog logn)re-spectively; for d ≥ 5 the function λ_(d-1)(n)is a slowly increasing function. These lower boundsare the greatest known ones for all even d and for d = 3. For d 2, 3, these estimates havebeen obtained in earlier studies of the author.
展开▼
