Proof of Lower Estimates for the Complexity of Self-Correcting Circuits by the Method of Basis Changing / Red'kin N.P. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2010. ? 3. P. 14-18 [Moscow Univ. Math. Bulletin. Vol. 65, No 3, 2010. P. 107-110].

A method for obtaining new lower estimates for the implementation complexity of individual Boolean functions is presented in the paper. The method is based on the transition from some considered basis to another one possessing already known good lower estimates for the complexity of those functions. The effective use of this method is illustrated by the example of obtaining the asymptotic value for the implementation complexity of threshold functions by self-correcting circuits composed of multiple-input elements.

Key words: Boolean functions, self-correcting circuits, implementation complexity of functions.