zbMATH — the first resource for mathematics

On estimates on the complexity of restrictions of Boolean functions. (English. Russian original) Zbl 0891.94012
Dokl. Math. 53, No. 3, 402-404 (1996); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 348, No. 5, 595-597 (1996).
The author finds lower bounds for the complexity of minimal contact and functional circuits that realize Boolean functions, in view of restrictions imposed on their domains. It is shown, in particular, that there exist partial functions having no circuits whose complexity and depth are close to the minimally possible ones at the same time. Proofs are not included.
Reviewer: I.Strazdins (Riga)

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30 Boolean functions
03D15 Complexity of computation (including implicit computational complexity)