Abstract:
Some operations over Boolean functions are considered. It is shown that the operation of the geometrical projection and the operation of the monotone extension can increase the complexity of Boolean functions for formulas in each finite basis, for switching networks, for branching programs, and read-$k$-times branching programs, where $k\ge 2$. It is established that if there exists a "big" gap between the complexities of realization of a function in the class of nondeterministic and in the class of deterministic branching programs (read-$k$-times branching programs), then it is possible to construct a function with a "big" gap between the complexity of realization of this function and the complexity of realization of its projection in the class of deterministic branching programs (read-$k$-times branching programs). It is shown that there is some relation between the operation of the geometrical projection and the operation of the monotone extension. Namely, it is shown that if there exists a function with a "big" gap between the complexities of realization of a function and its monotone extension in a class of schemata, then it is possible to construct a function with a "big" gap between the complexity of realization of this function and the complexity of realization of its projection in the same class of schemata. It is shown that there exist a functions of polynomial complexity and such that their monotone extension is a characteristic function of a NP-complete problem. The similar fact is valid for the operation of the geometrical projection. Namely, it is shown that there exist Boolean functions of polynomial complexity and such that their geometrical projection with respect to some subset of variables (the cardinality of this subset is less than the half of the cardinality of the set of variables) is the characteristic function of an NP-complete problem.