TR00-006 Authors: E.A. Okol'nishnikiva

Publication: 1st February 2000 12:22

Downloads: 996

Keywords:

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.