Okol'nishnikova E.A.
Sobolev Institute of Mathematics of Siberian Branch of Russian Academy of Sciences
(Novosibirsk)
The problem of finding nontrivial lower
bounds on the complexity of "well-defined" Boolean functions
is one of the most important problems in the mathematical
theory of complexity.
In the paper the computation of characteristic functions of
Reed-Muller codes by nondeterministic
branching programs is considered.
It is known that almost all Boolean functions can't be computed by
nondeterministic branching program of the size
less than
, where
is a constant.
But the best known lower bounds on the complexity
for nondeterministic branching
programs is the bound 
, obtained by
Pudlak [4] by the use of Nechiporuk method.
From the result of Razborov [2] for switch-rectifier
circuits follows the
bound on the complexity of
some symmetric Boolean functions for nondeterministic branching programs.
In [1] the bound
on the complexity of
characteristic functions of BCH-codes with a code distance
for deterministic branching programs was obtained.
In the paper we use a modification of a method
from [1] to obtain nonlinear lower bounds on the complexity
of characteristic functions of Reed-Muller codes for nondeterministic
branching programs.
Deterministic branching programs are a special case of nondeterministic branching programs.
Therefore all obtained bounds are valid for deterministic
branching programs too.
We use the programs with restrictions on the number of occurance
of each variable in each path
(namely, branching read-
-times only programs)
for obtaining lower bounds for programs without restrictions.
By
denote the complexity of a Boolean function
for nondeterministic branching programs.
Let , 
and 
be natural numbers, such that 
.
We introduce the following denotation:
Let us consider all possible representations of the function
as
 |
(4) |
, 
and 
are nonintersecting sets; 
;
, and
,
, 
.
By 
we denote the minimum number of disjunctive terms
in representation (4).
By 
we denote the maximum number of "ones" of a Boolean function
that belong to 
- faces of the cube.
By 
denote a Reed-Muller code
with a code distance 
[3].
A total number of variables of the characteristic function of
this code is equal to 
.
In order to obtain the main result of the paper we also
use the generalized Hamming weights for Read-Muller codes
considered by Wei [5].
as
,
.
Then
This research was supported by the Russian Foundation for Basic Research (Grant 00-01-00874) and the Federal program "Integration" (Project AO-110).
Ваши комментарии
|
![[SBRAS]](/gif/s_sigma.gif)
[Головная страница] [Конференции] [СО РАН] |
© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Wednesday, 03-Oct-2001 17:17:43 NOVST
be a Boolean function and 
, be a constant.
If for each subset of variables 
,
,
there exists a substitution of constants 
in the set
for nondeterministic
branching read-
-times only programs is not less than 
,
where 
is a growing function,
then 
.
, 
, 
, 
,
such that 
,
and 
,
calculated by formulas (1) - (3) are positive,
then
for
nondeterministic branching programs without restrictions
,
.