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

UptoLike

ВУЗ: 

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

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

Рубрика: 

NP NP
i X
i
=1 Y
j
=1 j ≤ i − 2 Y
j
=0j>
i−2
(X
1
∨ X
2
∨ Y
1
)&(X
3
∨ Y
1
∨ Y
2
)&(X
4
∨ Y
2
∨ Y
3
)& ...
&(X
p−2
∨ Y
p−4
∨ Y
p−3
)&(X
p−1
∨ X
p
∨ Y
p−3
)
(X
i
∨ Y
i−2
∨ Y
i−1
)
Y
1
Y
i−3
X
i
=1
ε
1
,...,ε
p
,α
1
,...,α
p−3
(X
1
∨ X
2
∨ Y
1
)&(X
3
∨ Y
1
∨ Y
2
)&(X
4
∨ Y
2
∨ Y
3
)& ...
&(X
p−2
∨ Y
p−4
∨ Y
p−3
)&(X
p−1
∨ X
p
∨ Y
p−3
).
α
1
=0 ε
1
=1 ε
2
=1
α
p−3
=1 ε
p−1
=1 ε
p
=1
α
1
=1 α
p−3
=0 i 1 ≤ i ≤ p − 4 α
i
=1
α
i+1
=0
(ε
i+2
∨ α
i
∨ α
i+1
)=1
ε
i+2
=1 ε
1
,...,ε
p
X
1
X
p
(X
1
∨
2
∨ ... ∨X
p
).
Ψ
(W )
Ψ(W ) Φ
3
(W )
n = |W |
W L(T )
T Ψ
3
(W )
NP

Страницы