Составители:
Рубрика:
Доказательство можно найти, например, в [3].
5.3. Класс NP-полных задач
Полиномиальная сводимость NP-полных задач
Если P≠NP, то между P и NPC=NP\P
имеется существенное различие.
Многолетняя мировая практика
разработки алгоритмов показывает, что
еще никому не удалось построить
алгоритм с полиномиальной временнóй
сложностью для некоторых классов
задач. Цель теории NP-полных задач в
доказательстве результатов вида: Если
P≠NP, то Π∈ NP\P.
NP
P
Рис. 5.1.
Важную роль в теории NP-полных задач играет полиномиальная
сводимость. Язык L
* *
полиномиально сводится к языку L⊆Σ ⊆Σ
1 1 2 2
,
если существует функция f: Σ
* *
→Σ
1 2
, удовлетворяющая двум
условиям.
1. Существует ДМТ-программа, вычисляющая f с
полиномиальной временной сложностью.
*
2. Для любого x∈Σ
, x∈L
1 1
в том и только том случае, если
f(x)∈L
.
2
сводится к L
Будем говорить “L
1 2
” (опуская слово “полиномиально”)
и писать L
∝
L .
1 2
∝
Утверждение 5.1. Если L
L , то из L ∈P следует, что L ∈P.
1 2 2 1
Доказательство можно найти, например, в [3].
и Π задачи распознавания, а Κ и Κ
Если Π
1 2 1 2
их схемы
кодирования, то будем писать Π
∝
∝
, если L Π (Π ,Κ )
1 2 1 1 1
L
(Π ,Κ ).
2 2 2
172
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
