Lower bounds on the complexity of local circuits. (English) Zbl 0609.94018

Jukna, S. P.

Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 440-448 (1986).

[For the entire collection see Zbl 0596.00021.]
The paper contains some initial ideas of a new technique for obtaining lower bounds on the complexity of Boolean circuits. The method consists in an appropriate concretization of an entropic approach to the lower bounds problem worked out by the author in Theory of Algorithms, Colloq. Pecs/Hung. 1984, Colloq. Math. Soc. Janos Bolyai 44, 251-270 (1986; Zbl 0601.03016). A combinatorial notion of ”entropy” of finite objects (Boolean circuits, Boolean functions, etc.) is defined. Lower bounds on the complexity are obtained by means of ”entropy preserving” imbeddings of circuits into the more restricted ones. To illustrate the technique, the model of ”local” contact circuits (including monotone circuits, one- time-only and real-time branching programs, circuits without null-chains, etc.) is considered. For such circuits, the technique allows to prove (in a uniform and easy way) that some naturally arising Boolean functions in NP require nearly-exponential (up to exp(\(\Omega\) (n))) size. For an extended and improved version of these results see the author’s paper ”Entropy of contact circuits and lower bounds on their complexity” [Theor. Comput. Sci. (to appear)].

MSC:

94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

complexity of Boolean circuits; Boolean functions

Citations:

Zbl 0596.00021; Zbl 0601.03016