Элементы теории алгоритмов - 192 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

Составители: 

Рубрика: 

NP NP
(α
1
,...,α
n
)
a
1
x
1
+ ... + a
n
x
n
= b,
(α
1
,...,α
n
, 1 − α
1
,...,1 −α
n
)
(α
1
,...,α
n
,β
1
,...,β
n
)
(2
0
+2
3ns
a
1
) · α
1
+(2
3s
+2
3ns
a
2
) · α
2
+ ...
... +(2
3(i−1)s
+2
3is
a
i
) · α
i
+ ...
(2
3(n−1)s
+2
3ns
a
n
) · α
n
+
(2
0
+2
(3n+1)s
a
1
) · β
1
+(2
3s
+2
3(n+1)s
a
2
) · β
2
+ ...
... +(2
3(i−1)s
+2
(3i+1)s
a
i
) · β
i
+ ...
(2
3(n−1)s
+2
(3n+1)s
a
n
) · β
n
=
2
0
+2
3s
+ ... +2
3(i−1)s
+ ... +2
3(n−1)s
+2
3ns
b +2
(3n+1)s
(A − b).
L R
i α
i
+ β
i
=1
α
1
+ β
1
=1
mod 2
3s
α
1
+ β
1
≡ 1( mod 2
3s
).
α
1
+ β
1
=1 α
1
+ β
1
> 2
3s
L ≥ (2
0
+2
3ns
a
1
)α
1
+(2
0
+2
(3n+1)s
a
1
)β
1
>
(2
0
+2
3ns
a
1
)(α
1
+ β
1
) > 2
3s
+2
3ns
·2
3s
>R,
L = R
α
1
+ β
1
=1&... & α
i−1
+ β
i−1
=1.
mod 2
3is
2
3(i−1)s
(α
i
+ β
i
) ≡ 2
3(i−1)s
(mod2
3is
).

Страницы