Entropy of contact circuits and lower bounds on their complexity
type: Item
instance of: scholarly article
title: Entropy of contact circuits and lower bounds on their complexity
zbMATH Open document ID: 0655.94020
DOI: 10.1016/0304-3975(88)90166-1
author: Stasys Jukna
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: A new concept of entropy H(A) of a discrete object A (circuit, Boolean function, etc.) is used to obtain lower bounds on contact circuit complexity of Boolean functions. Intuitively, an entropy must ensure two constraints: (i) \(size(S)\geq \delta^{-1}H(S)\) for any circuit S and some small \(\delta >0\) (independent of S), i.e. no step of computation makes more than \(\delta\) information; and (ii) if S computes f then H(S)\(\geq H(f)\), i.e. any circuit contains not less information than its function. Then \(\delta^{-1}H(f)\) is the lower bound for L(f), the circuit size complexity of f. In well-known Andreev-Razborov's approach the entropy H(A) is defined as the distance \(\rho\) (A,\({\mathfrak A})\) of A from a special class of objects \({\mathfrak A}\). Then (ii) is trivial, and (i) is the main step of this approach. In the paper under review the entropy \(H^{\phi}(A)\) is defined to be the maximum number of ``unsimilar'' subobjects of A with respect to an appropriate relation of ``similarity'' \(\phi\). Then, for some \(\phi\), (i) becomes trivial with \(H(S)=H^{\phi}(S)\). To prove (ii), special relations \(\psi\) are found such that \(H^{\phi}(S)\geq H^{\psi}(f)\). (This is done via an entropy- preserving embedding of circuits into the more restricted ones). Hence, \(L(f)\geq \delta^{-1}H(f)\). In particular, this new argument allows to prove in a uniform and easy way that contact circuits (as well as branching programs) with bounded number of null-chains require \(\exp_ 2(\Omega (\sqrt{n}))\) size to compute some explicitly defined n-argument Boolean functions.
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 4070810
zbMATH Keywords: entropy
zbMATH Keywords: circuit
zbMATH Keywords: Boolean function
zbMATH Keywords: lower bounds
zbMATH Keywords: circuit complexity of Boolean functions
zbMATH Keywords: contact circuits
zbMATH Keywords: branching programs
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90166-1
OpenAlex ID: W1991547553
cites work: The monotone circuit complexity of Boolean functions
cites work: Q4726174
cites work: Bounds for Width Two Branching Programs
cites work: The complexity of symmetric functions in bounded-depth circuits
cites work: Q3694708
cites work: Q3735698
cites work: Q3751515
cites work: Q5545524
cites work: Q3690219
cites work: Lower bounds on monotone complexity of the logical permanent
cites work: Q4724549
cites work: Q4138141
cites work: Q3663188
cites work: Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
cites work: Q3757396
cites work: Q3347300
description: scientific article; zbMATH DE number 4070810