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

UptoLike

ВУЗ: 

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

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

Рубрика: 

NP NP
Q
T
= {q
0
,q
1
,...,q
s
}
δ : Q
T
\{q
0
}×A
t
−→ P (Q
T
×A
T
×{L, S, R }).
p U(A
1
,...,A
p
)
(A
1
∨ ... ∨ A
p
)& &
1≤i<j≤p
(¬A
i
∨¬A
j
).
ε
1
,...,ε
p
U(ε
1
,...,ε
p
)=1
i
0
ε
i
0
=1
T
T
A
n
Hi, t Ci, j, t Sj, t
A
0 ≤ t ≤ p(n) T
A
{Hi, t|i, t =0, 1, 2,...}.
Hi, t
t T i
A
t
U(H0,t,H1,t,...,Hp(n),t), A A
0
& A
1
& ... & A
p(n)
.
A O(p
3
(n))
Hk, t
1+1+logk +1+logt +1 O(log p(n)) A
O(p
4
(n)) k t
k t k
t {|}
Hk, t 1+1+k+1+t+1 O(p(n))
A O(p
4
(n))

Страницы