On bounds for complexity of circuits of multi-input functional elements

摘要

In this paper we suggest a method to find lower bounds for complexity of circuitsof functional elements. The essence of the method consists of replacing the initial, maybe quitecomplex, basis containing multi-input elements by a more simple basis, say, of two-input ele-ments, with subsequent use of known lower bounds for complexity of circuits in the simplebasis. The efficiency of this method is illustrated on particular examples of finding the asymp-totics and even precise values of complexities of realisation of special Boolean functions, mono-tone Boolean functions and functions with small number of ones.This research was supported by the Russian Foundation for Basic Research, grant 08-01-00863 and by the Program of the President of Russian Federation for support of leading sci-entific schools, grant 4470.2008.1.