Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.intsys.msu.ru/magazine/archive/v10(1-4)/andreev-695-760.pdf Äàòà èçìåíåíèÿ: Thu Jun 21 03:41:10 2007 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 00:06:26 2012 Êîäèðîâêà: IBM-866

. . , . .



, . . , . . .


. , . k - . : , , . , . , , . , . , . . . , . . . . .


06-01-00240.


696

. . , . .

1. -
. . (1961, [110]) . . (1966, [111]) , - , n (log n)
5/2 3/2

log log n

,

n . - n2 (. . , 1971, [112]). ~1 ~1 x1 = (x1 , . . . , x1 ), x2 (x2 , . . . , x2 ), . . . , xk (xk , . . . , xk ) ~ 1 l l l X
k ,l s

. = (j ~
1,1

,...,j

1,s

,...,j

k ,1

,...,j

k ,s

,

1,1

,...,

1,s

,...,

k ,1

,...,

k ,s

)

1j
i,t i,1

j

i,2

...

j

i,s

l,

i = 1, 2, . . . , k ; t = 1, 2, . . . , s.

~ f (x1 , x2 , . . . , xk ), f , ~~ ~ f x i i,t i,t j i = 1, 2, . . . , k , t = 1, 2, . . . , s. L(F ) f -.

{0, 1},

i = 1, 2, . . . , k ,

1.1 ([114]). k 1, l f (x1 , x2 , . . . , xk ) , L(f ) ~~ ~
~ L(f )

5, k 2, X 1 ,l , , ~ 1 l L(f ),





3 1 (x) = 1 - x + x2 . 2 2




697

1.2 ([114]). 1, l r 4, c0 , k f (x1 , x2 , . . . , xk ) Xlk,lr , , ~~ ~ ~ - L(f )
~

c

0

l r

-

3 2

L(f ).

1.3 ([114]). k 1, l r 4, g 1 (x1 ), . . . , gk (xk ) ~ ~ r ~ ~ f = g (g1 (x1 ), . . . , gk (xk )), L(f ) 1 c0 l r
3 2

L(g ).

k , k 3 l = 2k /k , n = 2k + k § l. y 2k y1 ,...,k , 1 , . . . , k ~ {0, 1}, x1 , . . . , xk . ~ ~
k

Fn (y , x1 , . . . , xk ) = ~~ ~
1 ,...,k {0,1}

y

1 ,...,

k

i=1

xi . . . x 1

i l

i

.

1.1 ([114]). L(Fn ) C C§ n5 /2 , (log n)3/2 log log n

.

2.
. . ,


698

. . , . .

(. . [95], . . [96, 97], M. S. Paterson [98], V. R. Pratt [99], N. Pip enger [100], Z. Galil [101], K. Mehlohrn [101, 102], I. Vegener [103], . . [104]). 1984 . . , n ). . . [107, 108] , 2 2O(log n) . [109] . . . . , , 2 n 3 n . .
1 -o(1)

(2

n

1 -o(1) 3

2.1. A-
A P , P , A- {&, }, A. L A (f ) , A- f . , LA (f ) = 0 f A, A 0, 1 f , Lc &,,0,1} (f ) LA (f ), {

Lc (f ) f B B . (x, y ) , : (x, x) = 0, (x, y ) = (y , x),




699

(x, z )

(x, y ) + (y , z ).

P , A A, n {u1 , u2 , . . . , un , . . .}. P , {|f1 () = f2 ()} {|f3 () = f4 ()} = (f1 , f2 ) ~ ~ ~ ~ ~ ~ (f3 , f4 ).

, (F (u1 , . . . , un , f1 ), F (u1 , . . . , un , f2 )) (f , B ) = max (f , g ),
g B f1 B1 f2 B
2

(f1 , f2 ) .

f P



, BP



. ,

(B1 , B2 ) = max max (f1 , f2 ),

B 1 , B2 P



f1 , f2 , . . . , fk , i {1, 2, . . . , k - 1} f i fi+1 , fi fi+1 . (f1 , . . . , fk ) =
i, f
i

(fi , f
f
i+1

i+1

), ).

(f1 , . . . , fk ) =
i, f
i



(fi , f
f
i+1

i+1

[1 , 2 ](f , g ) (a1 , a2 ), f 1 , . . . , fk , f1 = f 2 , g = f k , (f1 , . . . , fk ) 1 B1 , B2 P [1 , 2 ](f , g )


a1 ,

(f1 , . . . , fk ) 2

a2 .

f B1 g B2 , (a1 , a2 ), [1 , 2 ](B1 , B2 ) (a1 , a2 ).


700

. . , . .

A , f1 &f2 f1 f2 , f1 , f2 A. 2.1 ([109]). f P


, AP

, LA (f )

1,

1 , 2 [1 , 2 ](A , A) g P


(a1 , a2 ),

a1 , a2 > 0,

, LA (f ) - 1,

1 (0, g ) 2 (1, g ) 2.1 ([109]). f P


LA (g )

1 (0, f ) - a1 , 2 (1, f ) - a2 .

, AP



, LA (f )

0

1 , 2 [1 , 2 ](A , A) LA (f ) min (a1 , a2 ), a1 , a2 > 0,

1 (0, f ) 2 (1, f ) - 2 (1, A \ {0}) , a1 a2

.

2.2.
2.2 ([109]). R s |R| (r - 1)s + 1, r 2, s 1,

V1 , V2 , . . . , Vr R V0 ( ), V0 V1 V2 V1 \ V0 , . . . , Vr \ V0 .




701

2.3.
W F , w W F (w) U n = {u1 , u2 , . . . , un }, F (w1 ) F (w2 ) = F (w1 w2 ), F (w1 ) F (w2 ) = F (w1 w2 ).
F Kw F (w), F w = , Kw = 1. F E n , E n ~w n- , , F (w), . M , M (F ) f M , f F , K w w W . f M , w W F f , w1 , w1 w Kw1 f , F F f . Kw f f . , f M (F )

F () = , F (W ) = Un ,

f=
w
F f


K

F w

( 0). F ls F f s, RF (f ) F . RF (0) = 0. f , f M M (F , w, k , r ) f M (F ), F w f RF (f ) |w| + k ,


702 l

. . , . .
F |w |+s

(r - 1)s ,
i=1 k =1

s = 1, 2, . . . , k .

M (F , w, k ) = M (F , w) =

M (F , w, k , i), M (F , w, k ).

l(f ) f , R(f ) . r,k f M , l(f ) = r, 1 R(f ) k.

f , . t(F , k ) = max
w1 w2 W |w1 | k , |w2 | |w1 |+k

|F (w2 ) \ F (w1 )| , .



F r,k

=

r,t(F ,k )

2.3 ([109]). M , r 2, |w| k , f M (F , w, k ) \ M (F , w, k , r ) g M (F , w, k ) , g l(g ) (f , g ) f, l(f ) - 1, (1,
r,k

).

2.4 ([109]). M , |w| k, r 2, f M (F , w, k ) \ M (F , w, k , r ) g M (F , w, k , r ), g (f , g ) f,
r,k

l(f ) (1,

).




703

M F -, (f1 , f2 ) = 0, w, W , f M(F , k , r ) = M (F , , k , r ), (F , s) = K
F w 1

~

F w

=f

2

~

F w

.

| w W, |w| = s .

M(F , k ) = M (F , , k ).

2.5 ([109]). 1 , 2 M , 1 F - , r 2, k 1, [1 , 2 ] (M(F , k , r ) , M(F , k , r ))
2k

(a1 , a2 ),

a1 =
s=k +1

s § (r - 1)s § 1 (0, (F , s)) ,
2k

a2 = 2k § (r - 1) 2.2 ([109]). 1 , 2 M , 1 F - f M > 0 L
2k A

§

2

1,

F r,k

.



,r 2, |W | k 1, LA 0, ,

1 (0, f ) 2 (1, f ) - 2 (1, (F , k )) , a1 a2

a1 = +
s=k +1

s § (r - 1)s § 1 (0, (F , s)) ,
2k

a2 = + 2k § (r - 1)

A = M(F , k , r ).

§

2

1,

F r,k

.


704

. . , . .

2.4.
F , f R (f ) , F (f ) s s . f . (F , k ) = max |F (w)|.
w W |w |=k

2.3 ([109]). p (0, 1), |W | k 1, r 2, f M (F ), LA (f ) 0, F+1 (f ) 1, t(F , k ) 1, A = M(F , k , r ), k LA (f ) min
2k s=k +1

1 - l(f )e-pR (f ) - p (F , k ) , 2k (r - 1)2k (pt(F , k ))r s(r - 1)s F (f ) s l(f )



.

s (f ) f , s . 2.4 ([109]). p (0, 1), k R (f ) k + 1, = {&, , 0, 1}, L (f ) min l(f )
2k s=k +1

1, r

2, f M




,

1 - l(f )e-pR (f ) - pk , 2k (r - 1)2k (pk )r s(r - 1)s s (f )

.

2.5.





Ak k A. GF (q ) q p(x) = x 2 + c1 x + c2 , c1 , c2 GF (q ), GF (q ) . GF (q ), p(x). GF (q )2 = GF (q ) ½ GF (q ) : (a1 , a2 ) + (b1 , b2 ) = (a1 + b1 , a2 + b2 ), (a1 , a2 ) (b1 , b2 ) = (a1 b1 - c2 a2 b2 , a1 b2 + a2 b1 - c1 a2 b2 ).




705

, , GF (q 2 ). (a, 0) GF (q ) (a, 0) (a1 , b1 ) = (a a1 , a b1 ) = a (a1 , b1 ). GF (q ) 2 GF (q ): 0 (x, y ), 1 (x, y ) = x, 2 (x, y ) = y , (
2k +1

(x, y ),

2k +2

(x, y )) = (

2k -1

(x, y ), 2k (x, y )) (x, y ),

k

1.

n = q 3 {x
a,b,d

| a, b, d GF (q )} = Un = {u1 , u2 , . . . , un },

GF (q ) 3 Un .
2m

d(, a, b) = ~
i=0

i i (a, b),
2m+1

= (0 , 1 , . . . , ~

2m

) GF (q ) x

,

a, b GF (q ), , K . ~

K = ~ g
n,m

a,b,d(,a,b) ~

a,bGF (q ) GF (q ) ~
2m+1

(u1 , u2 , . . . , un ) =

2.1 ([109]). m , 2 m n1/3 , 8 ln n1/3

L (g C
n,m

)

C

2


m/2

m

.

, .


706

. . , . .

m=2 L (g
n,m

n1/3 . 16 ln n1/3
n
1/3-o(1)

)

2

.

², t, n0 2 ² t n0 , n = nt0 . W n 0 , w1 , w2 , . . . , wn ². w W , i {1, 2, . . . , n}, , ui F wi W. f
n,² t

(u1 , u2 , . . . , un ) =
w W, |w |=t

.

²-. 2.2 ([109]). ² 2
1 2²-1

t= n

,

L (f
n,² t

)

2

n

²-1 -o(1) ²(2²-1)

.

3.
, , , . , , . , . , , ,




707

. . . . . U F , u U , F (u) ( ). U , F (u) , u. , U L U . , , , . u f ( ), f = F (u). () f u L U (u), LU (f ) f , u . . f , , f . . , , . , 100- . , , , , . 1949 . . . [1] , . ,


708

. . , . .

LU (n) = max LU (f ),
f

n . L U (n) ( ) , , n , L U (n). . . LU (n) , , , , . . . [2, 5]. . . . , , . , , 100- 2200 . , , . , A , A ( A A, n ) , LU (A ) = max LU (f ).
f A

A. . . . . . [10, 11], , , , .




709

, , . . [12, 13]. , . . , , . , , , , . . . . [14] , f , , f . , . . . . . , . . . [15]. . . [16]í[19], . log n (o( log log n ), n- ) , - -. log n (o( log log n ))


710

. . , . .

n (o( log n )) . . [20, 21] . [22] , , , n 2o( log n ) .

(. . [23, 24], [25], . . [26]), . , . , , . , , . ( ) . , , , , . , , , , . . . , , , .




711

, , . . , , . . [30]. § , , 0, 1 ; § , , , , , , . . , (f g , f g , g ). , , ( ). ( ). . , A


712

. . , . .

A . , . . , . , . . , . , , . . , , . , . , . , . -




713

, . . - , . . . , , , , , . , . . . : § , § ,

§ . . ,

§ ,

§ , D3 , L1 , S6 P6 ( [27]).

. , ( ). . . . :


714

. . , . .

§ ,

§ ,

§ , .

. . . . , , . , . , : § , § -, § ,

§ , § - , § - ,

§ , § , § , § . . § ,




715

. , , , . . , . : § 2o(n) , n , § 2 .
ã
o

. , , . . . P M P . F M (f 1 , f2 , . . . , fk ) P , k , F (f1 , f2 , . . . , fk ) . [S ] () S . [S ] .

âá

n log n

-


716

. . , . .

S = F (f1 , f2 , . . . , fk ). S f () f [S ],

f g , g f . S (a b ) f


[S ] (f

(a,b)

[S ]),

, S (f 1 , f2 , . . . , fk ) ( a b ) f . , f


, f

[S ]

S , {, , (a, b)}, . : § § § , , .

. , , 1, 2, . . . , k , k . , . , &, . 1, 2, . . . , S , S . F , , k S - [F (f1 , f2 , . . . , fk )], . f1 , f2 , . . . , fk . i f i , i = 1, 2, . . . , k , , , ,




717

( & , ) , , . [F (f 1 , f2 , . . . , fk )] , . , [F (f1 , f2 , . . . , fk )] g1 , g2 , . . . , gk , gi fi , . i- , i- , . ( ) , , . 1 k , k , 1 p, p . k , k . (f 1 , f2 , . . . , fk ) 2 Cp . i 2 fi . C j -1 + i, 1 i

718

. . , . .

, L (F ) , F . L L L , , . : § M;

§ P , ; § , , , [0, ); § , , [0, ) (a) a . = M, LM , , . S = F (f1 , f2 , . . . , fk ),
k

§ L

M

;



F M,

L n S

,

(S ) =

-1

(n)LM (F ) +

((fi )) ,
i=1


-1

(a) = sup{b | (b)

a}.

S . f P (), L
,

(f ) = min L
S, f S

,

(S ),




719

{, , (a, b)}, f ( , a b ). A , L
,

(A



) = max L
f A

,

(f ),

{, , (a, b)}, . : m(f ) , , 2N (f ) , H(f ) f , (log ) f . m(f ) m1 (f ) : x x , log log x log x log x = L
,

log x, x 2, 0

4 x<4

(A



)

(n)

, log (n) = o(log (n)), L (A


)

(n),

, log log (n) = o(log log (n)), L (A ) (n).


720

. . , . .

L
,

(A



)

(n)

, log (n) = o(log (n)), L (A


)

(n),

, log log (n) = o(log log (n)), L (A ) (n). : L (A L (A




) (n) L (A

) (n) L (A



)

(n), L (A



)

(n);



) (n), L (A



) (n).

1 , 2 1 2 , f , , L1 , (f ) L2 , (f ). , , L


, ,

, L , ,

, L , ,

. x x 1 (x) = , 2 (x) = . logx log log x , M, LM , ,
2

M, LM , ,

1

M . .





721 )),

3.1 ([35]). log n = o(log H(A L (A


)

H(A )),



),

log log n = o(log log H(A L (A





) H(A



),

1 = , L , m, log x x , H(A ) A , log (), f A . . . . . . . 3.2 ([35]). A , M {, , }, (n) {, (n), (a(n), b(n))}, L log2 n = o(log (n)), L 1 = M, LM , H,
x logx (n)
2



(n)
1

(A



)

(n),

(A



)

(n),
x logx

, 2 = M, LM , m,

Qr f P , H(f ) r (N (f )),

(r , N (f ) f ), 1,r f , m1 (f ) = r (N (f ))

(r ). 3.1 3.2 .


722

. . , . .

3.3 ([35]). log 2 n = o(log r (n)), r (n) L (Q r r (n))),
r

2n ,

) r (n),

log 2 n = o(log r (n)), log 2 n = o(log (2n - L (
1, r

= , L , m,

x logx

) log C

r (n) 2n

,

.

= , L , 2N , log x x . log r f P , m(f ) r (N (f )), r . . 3.4 ([35]). log log n = o(log log r (n)), L (
r

)r (n). (n) {, (n), (a(n), b(n))}, ) (n),

. 3.5 ([35]). A P , L
(n)
0

(A



log log n = o(log log (n)), L
(n)

(A



) (n),

, , 0 = , L , m, log x x . log . . . R , H(R ) lim = > 0. n 2n .




723

3.6 ([35]). = , L , m,
x logx

.

L (R



) 2n ,

. . 3.7. A , D3 , L1 , S6 , P6 L (A = , L , m,
x logx

) H(A



),

.

. . S 2 S1 , S1 S2 , [S2 ], , [S 1 ]. ~ S = F (F ) , , : H (S ) ~ , F , L (S ) F , N (S ) , S . r 1 , r2 , 1 , r2 r S , L (S ) r1 (N (S )), H (S ) r1 (n) = r2 (n)
r1 ,r2

r2 (N (S )).
o(1)

. 3.8 ([35]). 1 r2 (n) 2cn , L ( c , log3 n = o(log r2 (n)),

, = , L , m,

) r2 (n),
x logx

.


724

. . , . .

. . . . . . . . . . . , A ,
n

lim

H(A ) > 0. 2n

. . 3.8 . 3.9 ([35]). A , ~ ~ L ({ F | F A }) H(A ), = , L , m,
x logx

.

~ ~ F , F = (f1 , f2 , . . . , fS ),
s s s

f

1

f
s

2

s

s

s

f

S

s

s

. a = (a1 , a2 , . . . , an ) ~ I (a) = 2 ~
n-1

a1 + 2

n-2

a2 + . . . + 2a

n-1

+ an .

MH F , I (a) ~ I (~) I (F (a)) b ~ I (F (~)). b




725

. . 3.8 . 3.10 ([35]). ~ ~ L ({ F | F MH = , L , m,
x logx

}) 2

n+1

),

.

. f P , f +k , P I (~) = I (a) + k b ~ (mo d 2n ) f
+k

(a) = f ~

+k

(~). b

. . 3.8 . 3.11 ([35]). 1 L ({ f , f = , L , m,
x logx +1

t(n)
+t(n)

2

o(n)

,


,...,f

|f P

}) 2n ,

.

. 3.12 ([35]). A P , log 2 n = o(log (n)), L (A 1 log (n) = o
log (n) log n

)

(n),

,
(n)

L = , L , m,
x logx

(A



)

(n),

.

x , , = , L , m, logx . .


726

. . , . .

3.13 ([35]). A L (A log3 n = o(log (n)), 1




)

(n),

log (n) = o(log (n)), L
(n)

(A



)

(n).

3.14 ([35]). A L (A


(n) = H(A


)

),

log3 n = o(log (n)), (n) L c
(n)

2cn ,

(A



) (n) log (n) = o(log (n)), 2, b(n) 2,

.

3.15 ([35]). (0, 1), a(n) log a(n) + log b(n) L
(a(n),b(n))

n (1 - ), 2 1n 2.

(P

)

. , . . , . . , f , , f . L (f ) .. f ,




727

. () . N1 P: 1) r = {f | m(f ) r (N (f ))}, r ; 2) 1,r = {f | m1 (f ) = r (N (f ))}, r ; r (N (f ))}, r 3) Qr = {f | H(f ) ;

4) . . ; 5) , D 3 , L1 , S6 , P6 . ^ N1 A N 1 ) log n, Q , , log log H(A r r log log n = o(log log r (n)). ^ 3.16 ([35]). A N1 , log (n) = o L
(n) .. log H(A ) log n

,

(A



)L

0 ..

(A



) ()

H(A ) . log log H(A )

. . [28], . . L k (F ) F , (a,b) L (F ) Lk (F ) k , , a b . , .


728

. . , . .


3.17 ([35]). f P Lk (f )

,
O (1) log5 n

m(f ) O (1) (1 + )+2 log m(f ) log logn

.

N2 : 1) ; 2) MH ; 3) {(f , f +1 , . . . , f +r(N (f )) ) | f P }, r , 1 r (n) = 2o(n) ; ï ï ï 4) {(f , f , f , f , . . . , f , f ) | f P }, r r (N (f ))

, 1

r (n) = 2

o(n)

;

^ ~ ~ A , A = { F | F A}. ^ ^ 2 = {A | A N2 }. N , S , [S ]. ^ 3.18 ([35]). A N1 N2 H(A 1 L
(n) k

)

2

log 6 n

,

log (n) = o(log H(A




)),

(A

) Lk (A



)

H(A ) . log H(A ) 2, b(n) 2,

3.19 ([35]). (0, 1), a(n) log a(n) + log b(n) L
(a(n),b(n)) k

n (1 - ), 2 1 2n . n

(P

)

[29]í[34]. .




729

, 80- . [36] , , .

4.
. f (x 1 , . . . , xn ), , (. . .), . . . . . . ., , . . . : . . . {x 1 , . . . , xn } n ( 23 ) . . ., . . [44, 48], . . . (. . . .) . . . (. . . .) . . . (. . . .) . , ( ) [41, 44]. . . . . . [37, 38, 44]. , , . . . ,


730

. . , . .

. . . (. . . .), . . . . . . . ., . . . . ., , . . . . . , . . , [41, 42, 43]. , , . . . . , , , ( ) . . . (. . . .) . , [43, 44]. , . , , , [37], , , . [38, 44], . . . . n n , , 2 2 . [50] , . 1) . . . . : ) n , n , ; ) n , n , .




731

2) . . . . . 3) . . . . . . . . . . . . . . . . [46]. , . . . . . . . . . , . - . . , . . . . . . , . A . |A| A n , 2A A ½ . . . ½ A. |A| = n, A n-n

. = (1 , . ~

n {1, . . . , n}, (n 1) n E2 {0, 1}. E2 . . , n ), i E2 i n . n n ~ = (1, . . . , 1) ~ = (0, . . . , 0). E2 1 0 ~
n n

1 0 I (, I ) i n , , ~ ~ i = 1 ( i = 0). ( ~ 1 ||) I . , ~ ~~ ~ n ~ ~ E2 . , ( ~ ~ ), 1 I 1 , , ~ I ~ ~ ~ ~ ~~ , . ~


732

. . , . .

V U = (V , U ). n V E2 , V - = (V , U ), U , V , , , ~~ ~~ n . , E 2 - n- . P2 , , E2 , P2 (n) , n {x1 , . . . , xn }. r x 11 . . . xrr , xi = xi , i i i i = 1, xi = xi , i = 0, xij . . . . i D = K1 . . . Km Kj . . . . D M (D ) . . . ., , . . . . . ( . . . ) f (x 1 , . . . , xn ) . . ., f (x 1 , . . . , xn ) (, ) f (x1 , . . . , xn ) . . . f (x1 , . . . , xn ) N f n E2 , f () = 1. K ~ ~ n r - NK E2 (n r ) r - , NK (n - r )- n- . K , f (x 1 , . . . , xn ), NK Nf K , , NK NK Nf . f (x1 , . . . , xn ) . . . . DC (f ). D f . . . ., D f f D , , M (D ) M (D ). . . . . D T (f ), f , . . . . D T (f ).




733

M (DT (f )) , M (DC (f )) \ M (DT (f )) f . f (x1 , . . . , xn ) g (x1 , . . . , xn ) , Nf = Ng , . . . D1 , D2 ( D1 = D2 ), M (D1 ) = M (D2 ). . . . , . C = (X1 , . . . , Xs ) X Y X . , Y C ( Y C ), X i C Xi Y = . Y C , C . C P (C ). , [40, 48]. , . . . . . . ., . , . . ., , . . ., . (l, k ) , (l, k ) l k 1 , . . . , k E2 ~ ~ k ~ | I 0 i | = l, E l , ~ ~ I k . l , k . , l k . . . ., (l, k ). , , l, l + 2 , .
i ~ i=1 2


734

. . , . .

{1 , . . . , k } k - ~ ~ (l, k ). J ((l, k )) = 1 , . . . , Ik }. : l M ~ M , = {i1 , . . . , is }, (s l) l . & ( ) = (i1 )& . . . & (is ), ( ) = (i1 ) . . . (is ). , (l, k ), F ((l, k )). .
l E2 , 1 {I1 ~ l

4.1. f F ((l, k )) , : 1) |M (DT (f ))| = l, M (D f ;
T

(f ))



2) f : l M (DT (f )), , P (F ((l, k ))) : N & ( ) NKi ,
f Ki M (Dc (f ))\M (f ( ))

( l ), F ((l, k )), .
l l , l,k s l, l k l s . n() , . n(l) = max n(); n(l) = min n(); n(l, k ) = max n(); ns (l) = max n().

, l 1 n(l) = l + 2, n(l) log 3 l, l + 1 ns (l) l + 2 l, s, [l] l 1, 1 s C l 2 . 4.2. : 1) l + 1 l + 2, C [l] k = Cl2 , . . . , Cl 2 ; n(l, k )
2 l
l [2]



l



l



l,k



l s

k

C

l

, n(l, k ) = l + 2,




735

2) l

n(l, k )

l + 2, l
2 l k

k < Cl2 ; min(l + 2, A), k + 2C [ 2 ] + 3, 2 k

3) max(k , k § log A=C 4) n(l, k ) []
k
k 2

)

n(l, k ) l

log 3 l, k = 1.

log2



min(l, C

[k] 2
k

k

l;

)

, n(l, k) 2 l k l, o(l) k , l. l s,k l,k , s . [l] l 1 s k Cl 2 s,k . , (l, k , s), , . , , l . [l] l, s, 1 s Cl 2 , K (l, s) [l] k - s k , s k C l 2 l [2]
K l,C




. l () =
C

[]
l 2 l

4.3. l () 1 - l, .
l s,k , , l k . . . ., s . . . . n s (l, k ), ns (l, k ) = max n(), , k , -

(l, s), l + 1 ns (l, k ) l + 2. , , , .



l,k s

á

l,k s

l

, 0



1.


736

. . , . .

. , , . . T m ( Gm ) (, ) m . n(T m ) = max n(); n(T m ) = min n(); n(Gm ) = max n(); m m m n(Gm ) = min n(), n() m
G T



T

G

, . : 4.4. n(T m ) 4.5. m 4.6. m log 3 m.

2 n(T m ) = m. 2 :

1) ] log 2 (m + 1)[+2 n(Gm ) (log 2 m)2 + c1 log 2 m + c2 , c1 = 16, c2 = 39. 2) log2 (m + 1) n(Gm ) ] log 2 (m - 1)[+2. [40, 41, 42] , . y F G , , , , , . . . . . . . . . , , . . ,




737

- , . . . . 50- , . . . . . . , , . . ., , . : . . ., . . ., , . . . . . . . . , . . . . . . . ., A-, , . . . . , , s [116]. lC , lT , lQ , lkp , lkp , lko lA . . .: , , , , s , . . . 2 A-; l min . . . , Y , k . . . lC k . . . P n ~ , {0, 1}n ; P n -


738

. . , . .

n ; P,m n , m ; P n P m , m {0, 1} n ; n,t Pm (n, t)-, ~n m {0, 1}n ; Pm1 ,m2 n Pm1 +m2 , 1 m2 . , n ; .

4.7 ([115]). P lC (f ) log 3 n
n-1 r =0

n 0,m

n 2 r

n-r

1-m§2

-n 2

r

1- 1-m§2

-n 2

r

n-r

,

m

2n - 1;
2[log n]

lC (f ) 1 = o(m), m log 3 n;

r =1

m § 2r n § 2 r

-r r

,

lC (f ) 2m § n § 2 1 m = O (1).

-m m

,

~n Pm1 ,m2 n, m1 m2 . lC [117]. 4.8 ([115]). f P : n (f ) , n - log m + log log n n - log m = o(n), 2n = O (2n - m); n - n - log m (f ) n , n - log m
n 0,m



n/2 n(1-)

739

2

m

2

, , (0, 1/2); (f ) = 2,

2

m

2

n/2

. . . [118].
n m1 ,m
2

m 2

n-1

4.9 ([115]). f P , s+1 s lkp (f ) 1+ § lkp (f ), +1 2 =
m1 +m m1
2

, m1 + m

2

log n, log

m2 log n

(1 + O (1)) log

m1 log n

.

.

, , P n , s , n m1 m2 2n-1 , s log log n . . [119].

m

n,t 4.10 ([115]). F P m : lmin (F ) mt Q(1) min m, , lkp (F ) 1 + o(1) + n m log log log n t log m

log n.

. . . ~ . P n n, . . . , . . . . . . . T (f ) T f . T (n) = max T (f ),
~ f P
n

T (n, m1 , m2 ) =

~n f Pm

max
1 ,m2

T (f ).

á



log n


740

. . , . .

4.11 ([115]). T min Tkp , f , , . . ., c , : T T (n, m1 , m2 )
min

(n) + Tkp (n)

2
c

c§n

Tkp (n, m1 , m2 )
min

(n § (m1 + m2 ))c § 2 § min {2 , 2
n m
2

(n § (m1 + m2 )) § 2 }+2

2§m
2

§2

2

n+1

,
m
2

2

2§m

-m

2

§

§ min {2n , 2 § min 2n , 2

},
1

2§m

.

. . . (. [116]) , , , . , , . . ., . , , , m1 + m2 = O (log n). . . . . , A B , TA , A, TB , B , c , T B (n) 2cn TA (n), . 4.12 ([115]). : 1) f . . .; 2) f , . . . ; 3) f K . . . ; 4) f . . .




741

. . [116] . , , , , . . 4.13 ([115]). ) f P l
T n

:

(f ) = lQ (f ) = lC (f ) lA (f ) lko (f ),
[log log n]+1

l

T

(f )

r =[log log n]

n § 2r § 2 r

-2

r

.

) 1 : í í í í í

m

~n 2n - 2 f P1,m

) m 2n , [1/2, 1) n f P0,m : log log (f ) n, 1 , 1- log Y (f ) (1 - )n dim f , (f ) =

(0, 1/2).

lQ (f ) lT (f ) lA (f ), lC (f ) = O (lA (f )), 0 1 lC (f ) lC (f ) + lC (f ), m = O (2n /n), lT = lQ (f ) = lC (f ), m (1 + ) § 2n ( 2 - 1)/ 2, lA (f ) = lC (f ), m (1 + ) § 2n-1 , lT (f ) = 0, log n 2n - m 2n-1 (1 - ),

. . .


742

. . , . .

[116] . ) 4.13. n , m 2n , [1/2, 2/3], P0,m , , . . [120, 121]. , 2n 2 . . . . , . . . . . . . . LB B , (B ) . 4.14 ([115]). f P : m LB (f ) (B ) , log n log n m n
1+o(1) n m

.

, m = O (log n) , . . . [122] . . . ., . 4.15 ([115]). f P m lmin (f ) § C (m, n) log n
n m




743 m n
o(1)

1 C (m, n) 2, log n . (g ) g .

.

4.16 ([115]). g n m : §n , (g ) 2 log n m = n(n - 1)(1 - 2
-

/2, - ln

log n.

1 . . [123]. L , . 4.17 ([115]). f P : 2n+1 L (f ) (1 + o(1)) . log log n
n

. . [124] .

5.
, , , . [53, 63] . , , . , . D = 1, D (. . .) , , 11 x1 12 x2 . . . 1n xn = 1, . . . m1 x1 m2 x2 . . . mn xn = 1.


744

. . , . .

N P - , N P - , , . , , N P - . [64]í[67] , , . . , , . [57, 63, 68]í[78] . . . , . [61, 63, 79]í[84]. , . . . . , . , . , [85]. , . , , [86]í[89] , , -




745

, . , . , , , . , . , . [90, 91] , , , . . . , . , . . ., . , 2 . . , , . . ., .


746

. . , . .

. , . M . |M | , M . n E2 {0, 1}, E2 a = (a1 , . . . , an ), ai E2 (i = 1, . . . , n). ~ n , E2 n- n. B P2 , , E2 . x, = 1 x = x, = 0 r x11 &x22 & . . . &xrr , xij . i i i (. . .) D (x1 , . . . , xn ) = K1 . . . Kt Kj . . . . d . . . ., , . f (x1 , . . . , xn ) n Nf E2 a , f (a) = 1. ~ ~ n , Nk E K r , n - r . ^ f (x1 , . . . , xn ) f (x1 , . . . , xn ) , ^ Nf Nf . , f (x1 , . . . , xn ) ^ f (x1 , . . . , xn ). |Nf\Nf | , ^ ^ (f , f ) |Nf \ Nf | ^

.




747

( ) A, ((a) - M )2 aA D = |A|

A , , a A (a). (a) aA M = |A|

. (n, m, t, r ) , . . ., : n, m , . . ., , t, r . (n, m, t, r ). G (n, m, t, r ), M G (n, m, t, r ). : (n, m, t, r ) M G = 2n (1 - (1 - 2-r )t )m .

, . As = {a1 , . . . , as } , Ps (Q) a As , Q. , A s s Q, lim P|s (Q) = 1. s As | f1 (x1 , . . . , xn ) = 1 . . = , . fm (x1 , . . . , xn ) = 1

5.1. r , M G , t2 -r - n ln n n, r , M G > 2n , (0, 1), t2-r ln n


748

. . , . .

(n, m, t, r ) 2n (1 - (1 - 2
-r t m

)) .

(n, m, t, r ) , 2 , : n, m, , , t, r . T (n, m, t, r ). Q T (n, m, t, r ), M Q (n, m, t, r ). 5.2. T (n, m, t, r ) M Q = 2 n-m (1 - (1 - 21-r )t )m . n , n. 5.3. (0, 1) ( ) (0, 1),
r r 4 2 ,m , M Q > 2 n t 1+( ) 1+( ) T (n, m, t, r )

2

n-m

(1 - (1 - 2

1-r t m

)) .

5.1. 5.2, m(1 - 21-r )t = o(1) T (n, m, t, r ) 2 n-m . , . . . , , , . . ., D (x1 . . . xn ) = K1 K2 . . . Kt , Ki (1 i t) , t D .




749

, , , [71], ti (1 i m), , . . , , . . ., . . . . D (x1 , . . . , xn ) G(D ), . . . D (x 1 , . . . , xn ), , . . . . D (x1 , . . . , xn ) , G(D ) . 2n -|Nf | (f ) = , n f , 2n f . D (R, , t) . . . t , R , , . (R, , t) . . . D (R, , t) a = (1 - 2
a 2 -R

, =

1 1 K1 K2 . . . Kt11 = 1, . . .

K

m 1

K

m 2

... K

m tm

=1

), b = 2

-R

-

a 4

2

-2

-R

, 1 =

a 2

+
1-R

a2 4

+ b, 2 =
-2R

+ b.
-R

, (R, , 1) = 1 - 2

, (R, , 2) = 1 - 2

+2

.

5.4. (R, , t) = 1 t (((R, , 2) - (R, , 1)2 )1-1 - 1 - 2 - ((R, , 2) - (R, , 1)1 )

t-1 2

).


750

. . , . .

5.2. R t, R - t . (R, , t) (1 - 2 -R )t . D (R, t) . . . t, R.
^ 5.5. . . . D D (R, t) . . . D t=0

t0 , ND ND , ^ ^ (D ) - (D ) t
0

1-2

-R

R

t0 -1 R

2

2

e

2

R! +

R e

R

.

. f (x1 , . . . , xn ), . . . D (x1 , . . . , xn ) = K1 K2 . . . Kt , Ki (1 i t) R. U1 U2 , ^ ^ f (x1 , . . . , xn ), . . . D (x1 , . . . , xn ) = ^ ^ ^ ^ ^ K1 K2 . . . Kt0 , , Nf Nf , t0 t, t ^ , ^ (D , D ) (|Nf | - |Nf |). ^ U1 U2 , . . , U1 U2 . , . . . ~ f1 (x) = 1 . . = . ~ fm (x) = 1 f i (1 m), i




751

^ , 5.5. ^ , , , . : ^ 1) ; ^ 2) ; ^ 3) .

^~ f1 (x) = 1 . ^ . = . . ^ fm (x) = 1 ~


[1] Shannon C. . The synthesis of two-terminal swithing circuits // Bell Syst. Techn. J. 1949. V. 28. N 1. P. 59í98. [2] . . - // . 1956. . 111. 6. . 1171í1174. [3] . . // . 1958. . 119. 1. . 23í26. [4] . . // . . 1958. . 1. 1. . 120í140. [5] . . // . 1960. . 3. . 61í80. [6] . . ( ) // . 1962. . 7. . 61í114. [7] . . // . 1963. . 10. . 63í97.


752

. . , . .

[8] . . - // . 1964. . 11. . 25í47. [9] . . // . 1970. . 23. . 43í81. [10] . . , // . 1957. . 12. . 6. . 189í196. [11] . . // . 1959. . 2. . 75í121. [12] . . // . 1961. . 140. 2. . 322í325. [13] . . // . 1965. . 14. . 31í110. [14] . ., . . // . 1960. . 134. 3. . 543í547. [15] . . // . 1964. . 159. 2. . 290í293. [16] . . // . 1968. . 179. 4. . 786í789. [17] . . // . 1968. 5. . 40í48. [18] . . // . 1969. . 21. . 5í102. [19] . . // . 1973. . 26. . 19í26. [20] . . // . 1978. . 33. . 119í138.




753

[21] . . , I I // . 1979. . 36. . 195í208. [22] . // . 1978. . 241. 6. . 1273í1276. [23] . . // . 1964. . 12. . 29í37. [24] . . // . 1970. . 16. . 38í43. [25] . // . 1974. . 15. 6. . 937í944. [26] . . // . 1983. . 40. . 269. [27] . ., . ., . . . .: , 1966. [28] . . // . 1960. . 3. . 61í80. [29] . . // . 1984. . 277. 3. . 521í525. [30] . . // . 1985. . 127 (169). 6. . 147í172. [31] . . // . 1: , . 1985. 4. . 83í87. [32] . . // . 1985. . 283. 2. . 265í269.


754

. . , . .

[33] . . / 259 . . . . 1985. . 1í67. [34] . . // 7- , . , 1985. . 9í10. [35] . . / . . 1985. [36] . . // . 1985. . 281. 2. . 1033í1037. [37] . . // . . 10. .: , 1963. . 5í61. [38] . . // . . 2. : , 1964. . 3í9. [39] . . . . . // . . 19. .: , 1974. . 151í166. [40] . . - // . . 8. .: , 1962. . 5í14. [41] . . // . 139. 6. 1961. . 1329í1331. [42] . . // . 1. 1965. . 12í19. [43] . . // . 158. 5. 1964. . 1018í1021. [44] . . 1. .: , 1974. . 67í148. [45] . . // . . 38. .: , 1981. . 5í108.




755

[46] . . // . . 10. : , 1967. . 91í119. [47] . . .: , 1970. [48] . . k - // . 51. .: , 1958. . 5í142. [49] Katona G. A theorem of finite sets, Theory of Grah. New York, London, 1969. P. 187í208. [50] . // . [51] . // IV . , 1982. [52] . // . [53] . ., . . // . . . 1980. 3. . 123í129. [54] Menicon G. Umfassende Rechnerprogramme Losung vielschichtiger Luverlassigkeitsprobleme // Elek.-Nachr. 1973. N 3. S. 267í276. [55] . . . .: , 1971. [56] . ., . . , // . .: . . 41í52. [57] . ., . . . .: , 1984. [58] . ., . ., P. M., . ., . ., . . - // . 1971. . 13. 2. . 30í42. [59] . . . : , 1978.


756

. . , . .

[60] P. M., . . // . 1971 . . ., 1973. . 194í204. [61] . . , // . . . . 24. 10. . 1590í1595. [62] . . k - // . . 1958. . 51. . 5í142. [63] . . . : , 1982. [64] . . // . 1973. 3. . 12í15. [65] Skala Helen. The general solution of an arbitrary Bo olean equations // Amer. Math. Monthly. 1967. 74. N 9. . 1074í1077. [66] Bo chman D., Posthoff Ch. Die Behandlung Bo oliacher Oleichungen mit Hilfe des Bo oleschen Differentialkalkuls // Sitrungsb er Akad. Wiss. DDR. Math.-Naturwiss.-Tech. 1979. N 12. S. 5í25. [67] Bankovic Dragic. Solving systems of arbitraty equations // Discrete Math. 1983. 46. N 3. P. 305í309. [68] Antoniu Svob o da. An Algorithm for solving Bo olean Equations // IEEE Trans. compt. Vol. ECí12. 0ct. 1963. N 5. P. 557í560. [69] . . // . : , 1982. . 41í58. [70] . . . . // . , 1984. . 74. . 68í73. [71] . . . : , 1975. [72] . . // . . . . 1962. . 2. 1. . 186í189.




757

[73] Tapia Moier A., Tucker Jerry H. Complete solution of Bo olean equations // IEEE Trans comput. 198. 29. N 7. . 662í665. [74] Vaquero A., Iglesias M. Aplicacion del meto do de resolution de S.E.B. de Tagia and Tucker a la sintesis de funkiones multiples // Revista inf. autom. 1983. 16. N 58. P. 35í39. [75] Brown F. M. Reduced solution of Bo olen equations // IEEE Trans. comput. Vol. Cí19. Oct. 1970. P. 970í981. [76] ., . // . 1964. 25. 3. . 374í381. [77] . . // . . . . 1972. 2. . 114í124. [78] Follinger Otto. Die Losung Bo olischer Glecichungen // Elektron Datenverard. 1965. 5. N 6. S. 253í260. [79] . . // . . . . 1976. 4. . 1073í1077. [80] . . NP- . .: , 1984. [81] . . // . - . . . . . , 1984. [82] . . // . : , 1985. . 37í61. [83] Peeva . Sistems of linear equations over a b ounded chain // Acta Cyb ernetica. 7. Fas. 2. Forum centre publ. cyb ern. Hungaricum Szeged. 1985. P. 195í202. [84] . . . . // . . . . 1975. 15. 6. . 1568í1579. [85] . . // . . -. 1975. . 2. . 120í128. [86] . . // . 1981. 256. 3. . 521í524.


758

. . , . .

[87] . . / . . . .-. . .: , 1981. [88] . . // . . 41. . 117í141. M.: , 1984. [89] . . // . . 34. . 169í186. .: , 1978. [90] . . // . . 1981. 72. 2. . 67í72. [91] . . , // , . ., 1980. . 64. . 124í130. [92] . . T. 1. M.: , 1984. [93] / . . . . T. 1. M.: , 1974. [94] . . . .: , 1975. [95] . . - // . 1962. . 8. . 117í122. [96] . . // . 1969. . 21. . 237í240. [97] . . // . 1970. . 23. . 291í294. [98] Paterson M. S. Complexity of monotone networks for b o olean matrix pro duct // Theoretic Computer Science. 1975. V. 1. P. 13í20. [99] Pratt V. P. The effect of basis on size of Bo olean expressions // Pro c. of 16th Ann. Symp. Found. of Comp. Sci. New York, 1975. P. 119í121.




759

[100] Pip endger N. On another Bo olean matrix // IBM Research Rep ort RCí6914. 1977. [101] Mehlhorn K., Galil Z. Monotone switching circuits and Bo olean matrix pro duct // Computing. 1976. V. 16. P. 99í111. [102] Mehlhorn K. Some remarks on Bo olean sums // Acta Informatica. 1979. V. 12. P. 371í375. [103] Wegener I. Switching functions whose monotone complexity in nearly quadratic // Theoretical Computer Science. 1979. V. 9. P. 83í97. [104] . . {&, , 0, 1} // . 1984. . 41. . 81í98. [105] . . // 248 . 1985. . 1í15. [106] . . // . 1985. . 282. . 1033í1037. [107] . . // . 1985. . 281. 4. . 798í801. [108] . . // . . 1985. . 37. 6. . 887í908. [109] . . // . 1987. 1. . 3í26. [110] . . &, , ì // . 1961. . 136. 3. . 553í555. [111] . . // . 1966. . 169. 4. . 765í767. [112] . . - // . 1971. . 10. 1. . 83í92.


760

. . , . .

[113] . . () // . 1984. . 21. . 3í54. [114] . . - // . -. . 1: , . 1987. 1. . 70í73. [115] . . // . 1984. . 274. 2. . 265í269. [116] . . . // .: , 1974. [117] . . // . 1964. . 158. 4. . 770í773. [118] . . // . 1968. . 180. 1. . 32í35. [119] . . // - . , 1980. . 88í98. [120] . . // . 1966. . 171. 1. . 13í16. [121] . . // . , 1978. . 32. . 21í33. [122] . . // . .: , 1969. . 21. . 215í226. [123] . . // . , 1980. . 35. . 15í44. [124] . . // . , 1981. . 37. . 51í64.