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

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.

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) |