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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§1 NP
|((Z ∨ X ∨ Y )&(Z ∨ X ∨ Y ))|≤2 ·|(Z ∨ (X ≡ Y ))|.
D
E
ijkt
E
n = |W |
Ψ(W )
Ψ
(W )
n
3
p ≥ 4
(X
1
∨ X
2
∨ ... ∨ X
p
),
X
1
X
p
(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
∨ A
p
∨ Y
p−3
),
Y
1
Y
p−3
ε
1
,...,ε
p
A
1
A
p
(A
1
∨ A
2
∨ ... ∨ A
p
)
α
1
α
p−3
Y
1
Y
p−3
ε
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
,...,ε
p
X
1
X
p
(X
1
∨ X
2
∨ ... ∨ X
p
),

Страницы