Proof of lower estimates for the complexity of self-correcting circuits by the method of basis changing |
| |
Authors: | N P Red’kin |
| |
Institution: | 1.Faculty of Mechanics and Mathematics,Moscow State University,Leninskie Gory, Moscow,Russia |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|