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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§1 NP
p(n)
B
0 ≤ t ≤ p(n)
B
{Ci, j, t|i, j, t =0, 1, 2,...}.
Ci, j, t
t i a
j
T
B
i,t
U(Ci, 0,t,Ci, 1,t,...,Ci, m, t).
B
i,t
i t
T
A
T
= {a
0
,a
1
,...,a
m
},
A
T
T
B
i,t
O(1)
B &
0≤i≤p(n)
0≤t≤p(n)
B
i,t
.
Q
T
= {q
0
,q
1
,...,q
s
},
Q
T
T
B O(p
2
(n))
B O(p
3
(n))
C
0 ≤ t ≤ p(n) T
C
{Sk, t|k, t =0, 1, 2,...}.
Sk, t
t T q
k
C
t
U(S0,t,S1,t,...,Ss, t), C C
0
& C
1
& ... & C
p(n)
.

Страницы