Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

NP-полные задачи. Теорема Кука




 

Если P ¹ NP, то задачи из NP \ P являются труднорешаемыми. Цель дальнейших результатов состоит в доказательстве того, что существуют конкретные задачи П, для которых справедливо включение П Î NP \ P, если P ¹ NP. Соответствующие результаты основаны на понятии полиномиальной сводимости задач. Пусть П1, П2 — две задачи распознавания, задаваемые в алфавитах А 1 и А 2 соответственно. Будем говорить, что задача П1 полиномиально сводится к задаче П2 (обозначение: П1 µ П2), если существует словарная функция такая, что выполнены условия:

f — полиномиально вычислима;

выполнено: х — индивидуальная задача П1 с ответом «ДА» Û — индивидуальная задача П2 с ответом «ДА».

Утверждение 18.2. Если выполнено П1 µ П2 и П2 Î P, то П1 Î P.

Доказательство. Предложим полиномиальный алгоритм решения задачи П1: находим f (x) Î П2 и применяем к f (x) полиномиальный алгоритм, существующий по условию. Если получен ответ «ДА», то х имеет ответ «ДА». В противном случае х имеет ответ «НЕТ». Время работы алгоритма не превосходит , где pf — полином, ограничивающий время вычисления функции f, участвующей в сведении П1 µ П2, p 2 — полином, ограничивающий время решения задачи П2. Доказательство завершено.

Утверждение 18.3. Если выполнено П1 µ П2 и П2 µ П3, то П1 µ П3.

Доказательство очевидно, так как функция f 3(x) = f 2(f 1(x)) осуществляет сведение П1 µ П3, если f 1, f 2 дают сведения П1 µ П2, П2 µ П3 соответственно.

Определение 18.4. Задача П называется NP - полной, если выполнено:

а) П Î NP;

б) П1 µ П для любой задачи П1 Î NP.

Задача П называется NP - трудной, если для нее выполнено условие б).

Обозначим через NPС класс NP -полных задач, а через NPН — класс NP -трудных задач.

Согласно определению имеем:

NPС Ç P ¹ Æ Þ P = NP,

NPH Ç P ¹ Æ Þ P = NP,

NPС Ç (NP\P) ¹ Æ Þ NPС Ç P = Æ.

Другими словами, если для какой-то NP -полной задачи существует полиномиальный разрешающий алгоритм, то и для любой задачи из класса NP существует полиномиально разрешающий алгоритм. То же высказывание справедливо относительно NP -трудной задачи. Если какая-то NP -полная задача не лежит в классе Р, то и все NP -полные задачи не лежат в классе Р.

Утверждение 18.4. Если задачи П1, П2 Î NP, П1 µ П2 и П1 Î NPС, то П2 Î NPС.

Доказательство. Пусть П Î NP — произвольная задача. Тогда по определению П µ П1. Поскольку по условию П1 µ П2, то согласно утверждения 18.3 имеем П µ П2, что и доказывает данное утверждение.

Отсюда получаем способ доказательства NP -полноты конкретных задач, используя полиномиальное сведение к ней другой NP -полной задачи. Этот же способ пригоден и для доказательства NP -трудности задачи. Напомним, что классы NPC и NPH определяются только выполнимостью условий а), б) для NPC и условия б) для NPH.

Докажем теперь важную теорему Кука С. (1971), дающую первый пример NP -полной задачи.

Теорема 18.5. Задача проверки выполнимости произвольной КНФ является NP -полной задачей.

Доказательство. Пусть ВЫП — идентификатор данной задачи. В предыдущем разделе было показано, что ВЫП Î NP. Пусть П — произвольная задача из NP. Необходимо показать, что П µ ВЫП. Для этого множество индивидуальных задач L П с ответом «ДА» представим в стандартном виде соответствующей недетерминированной машиной Тьюринга (обозначение: НДМТ), работающей полиномиальное время и принимающей множество L П. Такое представление дает общую сводимость задачи, решаемой НДМТ за полиномиальное время.

Пусть распознающая множество L П НДМТ имеет алфавиты А, Q и функцию переходов (программу) , р (n) — верхняя граница времени вычисления. Функцию fL, осуществляющую полиномиальное сведение П µ ВЫП, опишем в терминах работы НДМТ.

В вычислениях участвуют ячейки ленты с номерами от - р (n) до р (n) + 1, и при этом требуется учесть не более р (n) + 1 тактов работы НДМТ. Проверяющее вычисление определяется заданием в каждый момент времени содержания ячеек с указанными номерами, внутреннего состояния машины и положения считывающей головки. Соответствующие вычисления опишем в виде КНФ, использующей полиномиальное число дизъюнкций. Фиксируем нумерацию в алфавитах:

.

Условимся, что фраза «в момент времени i» означает «после выполнения i -го шага работы». Если вычисление закончилось раньше времени p (n), то конфигурация не меняется во все моменты после остановки. В нулевой момент на ленте записано слово х в ячейках с номерами 1, …, n. Слово-догадка w пишется в ячейках с номерами –1, …, –| n|. Остальные ячейки пусты. Описывая принимающее вычисление, необходимо учесть, что:

а) в ячейках пишется точно один символ;

b) машина находится точно в одном состоянии;

с) головка может просматривать точно одну ячейку с номером от – p (n) до p (n) + 1;

d) машина работает по программе.

Определим сначала переменные и их смысл с помощью табл.18.2.

 

Таблица 18.2

 

Переменная Пределы изменения индексов Смысл
Q (i, k) 0 £ i £ p (n) 0 £ k £ r В момент времени i машина находится в состоянии qk
H (i, j) 0 £ i £ p (n) – p (n) £ j £ p (n) + 1 В момент времени i головка просматривает ячейку с номером j
A (i, j, k) 0 £ i £ p (n) – p (n) £ j £ p (n) + 1 0 £ k £ r В момент времени i в j -ю ячейку записан символ ak

 

Описание сводящей функции fL для П µ ВЫП дадим в виде набора дизъюнкций, конъюнкцией которых и будет fL. При этом выполняющий набор значений истинности однозначно соответствует принимающему вычислению на х, стадия проверки занимает время не большее p (n) шагов, слово-догадка имеет длину не более p (n), причем:

x Î L П Û на х существует принимающее вычисление;

Û на х существует принимающее вычисление с временем £ p (n) и | w | £ p (n);

Û существует выполняющее значение переменных для задачи fL (x), заданной КНФ.

При этом fL (x) вычисляется за полиномиальное время.

Определим множества дизъюнкций и их смысл.

G 1 в любой момент времени i машина находится точно в одном состоянии;

G 2 в любой момент времени i головка просматривает точно одну ячейку;

G 3 в любой момент времени i каждая ячейка содержит точно один символ А;

G 4 в момент времени 0 вычисление находится в начальной конфигурации стадии проверки со входом х;

G 5 не более чем через p (n) шагов машина переходит в состояние qY (принимает х);

G 6 для любого момента времени i, 0 £ i £ p (n) конфигурация машины в момент i + 1 получается из конфигурации в момент i однократным применением команды машины.

Описание дизъюнкций для функции fL.

 

G 1 (Q (i, 0) Ú Q (i, 1) Ú … Ú Q (i, r)) 0 £ i £ p (n)
0 £ i £ p (n) 0 £ i < j’ £ r
G 2 (H (i, ‑ p (n)) Ú H (i, ‑ p (n) + 1) Ú … Ú Ú H (i, p (n) + 1)) 0 £ i £ p (n)
0 £ i £ p (n) – p (n) £ i < j’ £ £ p (n) + 1
G 3 (a (i, j, 0) Ú a (i, j, 1) Ú … Ú a (i, j, v) 0 £ i £ p (n)
‑p (n) £ j £ p (n) + 1 0 £ k < k’ £ v
G 4 (Q (0, 0)), (H (0, 1)), (a (0, 0, 0)), (a (0, ‑1, 0)), …, (a (0, ‑ p (n), 0)), (a (0, 1, k 1)), …, (a (0, n, kn)), (a (0, n + 1, 0)), …, (a (0, p (n) + 1, 0)), где  
G 5 (Q (p (n), 0))  
G 6 а) Замечание. Дизъюнкция гарантирует, что если головка машины в момент i не просматривает ячейку j, то в момент i + 1 ее содержимое не меняется 0 £ i £ p (n) ‑p (n) £ j £ p (n) + 1 0 £ l £ v
б) , где D, l, k ’ определены командами машины: если qk Î Q \{ qY, qN }, то qk al à qk al D; если qk Î { qY, qN }, то D = 0, k’ = k, l ’ = k 0 £ i £ p (n) ‑p (n) £ j £ p (n) + 1 0 £ l £ v

 

Заметим, что число дизъюнкций в G 6 — полином от n. Далее, если x Î L П, то существует принимающее вычисление длины не большей p (n) и выполнимы все дизъюнкции из G 1, G 2, G 3, G 4, G 5, G 6, и x Î L П тогда и только тогда, когда существует выполняющий набор для fL = G 1 × G 2 × G 3 × G 4 × G 5 × G 6. Теперь, для любого x Î L П индивидуальная задача fL (x) может быть построена за время, ограниченное полиномом от n = | x |, при этом длина fL (x) также ограничена сверху полиномом от n.

Таким образом, преобразование fL (x) может быть осуществлено за число действий, полиномиально зависящее от n. При этом fL (x) имеет O ((p (n))2) переменных и O ((p (n))2) дизъюнкций. Так как П — произвольная задача из NP, то тем самым теорема доказана.

 




Поделиться с друзьями:


Дата добавления: 2014-12-29; Просмотров: 1054; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.031 сек.