Lower estimates for the complexity of realization of characteristic functions of binary codes by binary programs. (Russian) Zbl 0819.94031

Okol’nishnikova, E. A.

Metody Diskretn. Anal. 51, 61-83 (1991).

Summary: Nonlinear lower estimates have been obtained for the realization complexity of sequences of characteristic functions of binary codes with a large number of code vertices and increasing (with increase of \(n\)) code distance by binary programs and formulas in the base \((\vee, \&, \neg)\). In particular, the estimate \(C\cdot n\cdot \ln n/\ln\ln n\) has been obtained for characteristic functions of BCH codes (with code distance \(\ln n/\ln \ln n\)) in the class of binary programs.
Let \(BP_ k\) be the class of binary programs, where every path contains at most \(k\) testing of the same variable. It has been shown that in case \(k= c_ 1\ln n/\ln \ln n\), where \(0<c_ 1<1\), a binary linear code exists, the complexity of realization of the characteristic function of which in the class \(BP_ k\) is not less than \(\exp (n^{(1-c_ 1)/2})\). The complexity of realization of the same function in the class of binary programs without constraints is not less than \(2 n^ 2\), i.e. a constraint on the number of testings in a chain with respect to each of the variables gives exponential growth (with respect to the number of variables) of the complexity of the binary program.

MSC:

94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30	Boolean functions
94B05	Linear codes (general theory)

Keywords:

realization of Boolean functions; nonlinear lower estimates; binary programs; binary linear code