zbMATH — the first resource for mathematics

Local complexity of Boolean functions. (English. Russian original) Zbl 1028.68062
Discrete Appl. Math. 135, No. 1-3, 55-64 (2004); translation from Diskretn. Anal. Issled. Oper., Ser. 1 4, No. 3, 69-80 (1997).
Summary: Classes of locally complex and locally simple functions are introduced. The classes are proved to be invariant with respect to polynomially equivalent complexity measures. A relationship is considered between proving that a function belongs to a class of locally complex functions and proving lower bounds for Boolean circuits, switching circuits, formulas, and $$\pi$$-circuits (formulas over the basis $$\{\&,\vee,{}^-\}$$).
MSC:
 68Q25 Analysis of algorithms and problem complexity 06E30 Boolean functions 90C10 Integer programming
Full Text:
References:
 [1] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1976), Addison-Wesley Reading, MA [2] Chashkin, A.V., Complexity of restrictions of Boolean functions, Diskret. math., 2, 133-150, (1996), (in Russian) · Zbl 0891.94012 [3] Chashkin, A.V., Lower complexity bounds for restrictions of Boolean functions, Discrete appl. math., 114, 61-93, (2001) · Zbl 1006.94035 [4] R. Lidl, H. Niederreiter, Finite Fields, Vol. 1, Addison-Wesley, Reading, MA, 1983. · Zbl 0554.12010 [5] O.B. Lupanov, Asymptotic Bounds for Complexity of Control Systems, Mosk. Gos. University, Moscow, 1984 (in Russian). [6] R.G. Nigmatullin, Lower Complexity Bounds and Complexity of Universal Circuits, Kazan. Gos. University, Kazan, 1990 (in Russian).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.