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

UptoLike

ВУЗ: 

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

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

Рубрика: 

NP NP
p
Σ
j=1
x
(0)
j
≤ h
t
·b −
n
Σ
j=p+1
h
t
· u
j
· x
(0)
j
≤
mC
1
D +(n − p)mCC
2
1
≤ M.
(x
(0)
1
,...,x
(0)
n
) M
a
11
x
1
+ ... + a
1n
x
n
≤ b
1
... ...
a
m1
x
1
+ ... + a
mn
x
n
≤ b
m
M
1
=(n + m) · (mC)
2m+3
· (D +1).
x
1
x
n
Ax ≤ b
x
1
x
n
y
1
y
m
(A, E
m
)[x, y]=b
L
Ax = b Ax ≤ b
L = mn +log|P |,
P A b log |P |
A b mn
A
log M =logn +(2m +3)·(log m +logC)+log(D +1)=O(L
2
),
Ax ≤ b
Ax ≤ b NP
Ax = b
Ax ≤ b

Страницы