ECCC-Report TR00-006https://eccc.weizmann.ac.il/report/2000/006Comments and Revisions published for TR00-006en-usTue, 01 Feb 2000 12:22:23 +0200
Paper TR00-006
| On operations of geometrical projection and monotone extension |
E.A. Okol'nishnikiva
https://eccc.weizmann.ac.il/report/2000/006
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.
Tue, 01 Feb 2000 12:22:23 +0200https://eccc.weizmann.ac.il/report/2000/006