ИДЗ Часть1 Вариант 10 (Общая подпоследовательность наибольшей длины)

Федеральное агентство по образованию

Липецкий государственный технический университет

Кафедра АСУ

Индивидуальное домашнее задание

по математической логике

«Доказательство принадлежности задачи классу NP»

Вариант 10

Студент

Группа

Руководитель Гаев Л. В.

Липецк 2007

Задание кафедры

10. ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ

УСЛОВИЕ. Заданы конечный алфавит Σ, конечное множество R слов из Σ* и положительное целое число К.

ВОПРОС. Существует ли такое слово w  Σ*, что |w| ≤ К и w - подпоследовательность каждого слова из R?

Опр. f(x) = O(φ(x)) <=> f(x) C·φ(x), С = const.

Этапы доказательства:

1) проверка принадлежности сгенерированной подпоследовательности w конечному множеству Σ;

2) проверка включения сгенерированной подпоследовательности w во все слова

ri  R (1 i  |R|).

Для проверки выполнения условия 1) необходимо проверить принадлежность каждой буквы сгенерированной последовательности w конечному множеству Σ. Для этого потребуется в худшем случае O(|w|·|Σ|) операций, где |w| и |Σ| - соответственно мощности w и Σ. А т. к. |w| ≤ K из условия, тогда, обозначая |Σ| = h, получаем O(K·h) операций.

Для проверки выполнения условия 2) необходимо выполнить поиск подстроки w в строках ri  R (1 i |R|). Для этого потребуется в худшем случае, когда w является последней буквой в слове ri, O(|w|·|ri|) операций, а т. к. |w| ≤ |ri| ≤K и количество строк ri =|R| тогда, обозначая |R| = t, получаем O(K²·t) операций.

Вывод: общее количество операций проверки равно O(K² ·t + K· h) – полином от начальных условий задачи => данная задача принадлежит к классу NP.

1. Отыскание некоторой задачи П’NPC.

В качестве данной задачи П’ будет выступать задача ВЕРШИННОЕ ПОКРЫТИЕ .

ВЕРШИННОЕ ПОКРЫТИЕ

Условие: Дан граф G=(V,E) и положительное целое число k, k|V|

Вопрос: Имеется ли в графе G вершинное покрытие не более чем из k элементов, т.е. такое подмножество V′V, что |V′|  k и для каждого ребра {u, v}E хотя бы одна из вершин u или v принадлежит V′?

Задача Вершинное покрытие является NP-полной.

2. Доказательство NP-полноты.

Доказательство NP-полноты будет проводить методом сужения. Докажем, что, наша исходная задача включает в качестве частного случая известную NP-полную задачу Вершинное покрытие. Суть состоит в том, чтобы указать дополнительные ограничения, которые требуется нало­жить на индивидуальные задачи из задачи ОБЩАЯ ОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ, чтобы получившаяся в результате сужения задача была бы эквивалентна задаче Вершинное покрытие.

Наложим ограничение на начальные условия задачи: пусть K=3 и |R|=1. То есть множество R содержит одно слово.

Тогда необходимо выбрать такое слово w, такое, чтобы |w|К w - подпоследовательность слова из R. Значит, данная задача сводится к известной NP-полной задаче “ ВЕРШИННОЕ ПОКРЫТИЕ ”.

Имеем, что задача ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ является частным случаем задачи ВЕРШИННОЕ ПОКРЫТИЕ при ограничении, что K=3 и |R|=1. Поэтому задача ОБЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ НАИБОЛЬШЕЙ ДЛИНЫ принадлежит к классу NP.

Т.к. задача доказывалась методом сужения, то полиномиальность преобразований очевидна (это вытекает из того, что на условие задачи накладывалось единственное ограничение K=3 и |R|=1).