Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-006 | 26th January 2000 00:00

On operations of geometrical projection and monotone extension

RSS-Feed




TR00-006
Authors: E.A. Okol'nishnikiva
Publication: 1st February 2000 12:22
Downloads: 972
Keywords: 


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.



ISSN 1433-8092 | Imprint