ВУЗ:
Составители:
Сводимость за полиномиальное время
Говорят, что язык L
1
сводится за полиномиальное время к языку L
2
(запись: L
1
≤
P
L
2
), если
существует такая функция f: {0, 1}
*
→ {0, 1}
*
, вычислимая за полиномиальное время, что
для любого x∈{0, 1}
*
,
x ∈ L
1
⇔ f(x) ∈ L
2
.
Функцию f называют сводящей функцией, а полиномиальный алгоритм F, вычисляющий
функцию f, – сводящим алгоритмом.
Теорема 40. Если язык L
1
⊆ {0, 1}
*
сводится за полиномиальное время к языку
L
2
⊆ {0, 1}
*
и L
2
∈ P, то L
1
∈ P.
Доказательство. Пусть A
2
– полиномиальный алгоритм, распознающий язык L
2
, а
F – полиномиальный алгоритм, сводящий язык L
1
к языку L
2
. Построим алгоритм A
1
,
который будет за полиномиальное время разрешать язык L
1
.
Рис. 2 иллюстрирует построение. Получив вход x∈{0, 1}
*
, алгоритм A
1
(с помощью
алгоритма F) получает f(x) и с помощью алгоритма A
2
проверяет, принадлежит ли слово
f(x) языку L
2
. Результат работы алгоритма A
2
на слове f(x) и выдается алгоритмом A
1
в
качестве ответа.
Определение полиномиальной сводимости гарантирует, что алгоритм A
1
дает
правильный ответ; он полиномиален, поскольку полиномиальны алгоритмы F и A
1
.
F
A
2
f(x)
f(x)
∈
L
2
?
A
1
x
f(x)∈ L
1
?
Рис. 2. Принадлежность слова x к языку L
1
можно проверить, использовав сводящий
алгоритм F и алгоритм A
2
, разрешающий язык L
2
.
Понятие сводимости позволяет придать точный смысл утверждению о том, что один язык
не менее труден, чем другой (с точностью до полинома). Запись L
1
≤
P
L
2
можно
интерпретировать так: сложность языка L
1
не более чем полиномиально превосходит
сложность языка L
2
. Наиболее трудны в этом смысле NP-полные задачи.
NP-полнота
Язык L ⊆ {0, 1}
*
называется NP-полным, если
1) L∈ NP;
2) L
′
≤
P
L для любого L
′
∈ NP.
Класс NP-полных языков будем обозначать NPC.
Основное свойство NP-полных языков состоит в следующем.
Теорема 41. Если некоторая NP-полная задача разрешима за полиномиальное
время, то P = NP. Другими словами, если в классе NP существует задача, не разрешимая
за полиномиальное время, то все NP-полные задачи таковы.
Доказательство. Пусть L
– NP-полный язык, который одновременно оказался
разрешимым за полиномиальное время (L∈P и L∈NPC). Тогда для любого языка L
′
по
свойству 2 определения NP-полного языка имеем L
′
≤
P
L. Следовательно, L
′
∈P (теорема
40), и первое утверждение теоремы доказано.
Второе утверждение теоремы является переформулировкой первого.
