Entropy of contact circuits and lower bounds on their complexity

AbstractA method for obtaining lower bounds on the contact circuit complexity of explicitly defined Boolean functions is given. It appears as one of possible concretizations of a more general “convolutional” approach to the lower bounds problem worked out by the author in 1984 [12]. The method is based on an appropriate notion of “inner information” or “entropy” of finite objects (circuits, Boolean functions, etc.). Lower bounds on the complexity are obtained by means of entropy-preserving embeddings of circuits into the more restricted ones. This allows to prove in a uniform and easy way that contact circuits, which are local in a sense that the function computed by a subcircuit weakly depends on the whole circuit, require 2Ω(√n) or even 2Ω(nlog n) contacts to compute some explicitly defined n-argument Boolean functions from NP