Составители:
Рубрика:
∝
∝
∝
Утверждение 5.2. Если L L и L L , то L L
1 2 2 3 1 3
(транзитивность). Доказательство можно найти, например, в [3].
∝
Языки L
и L полиномиально эквивалентны, если L L
1 2 1 2
и
L
∝
L
2 1
. Язык L называется NP-полным (L∈NPC), если L∈NP и любой
другой L′∈NP сводится к L.
По современным представлениям более точное соотношение между P, NP и NPC
показано на рис. 5.2.
∝
Языки L и L полиномиально эквивалентны, если L L
1 2 1 2
и
L
∝
L
2 1
. Язык L называется NP-полным (L∈NPC), если L∈NP и любой
другой L′∈NP сводится к L.
По современным представлениям более точное соотношение между P, NP и NPC
показано на рис. 5.2.
NP
P
N
PC
Рис. 5.2.
∝
Утверждение 5.3. Если L
и L ∈NP, L ∈NPC и L L
1 2 1 1 2
, то
L
∈NPC. Доказательство можно найти, например, в [3].
2
Теорема 5.2. Задача о выполнимости к.н.ф. есть NP-полная
задача.
Доказательство [14]. Доказательство основано на описании
работы машин Тьюринга с помощью к.н.ф.. Рассматриваем
произвольную переборную задачу Z
п
={z} распознавания свойства
R(z,y). Пусть машина Тьюринга M проверяет истинность R(z,y) за
время, ограниченное полиномом от суммы размерностей записи z и y
на ленте, т.е. l(z) + l(y). Длина l(y) не превосходит некоторого
полинома от l(z), поэтому время распознавания свойства R(z,y) и
требуемый размер активной зоны ограничены некоторым полиномом
173
Страницы
- « первая
- ‹ предыдущая
- …
- 87
- 88
- 89
- 90
- 91
- …
- следующая ›
- последняя »
