ИДЗ Вариант 18 (Разбиение на подматрицы со свойством связности)

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

ИДЗ

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

по дисциплине

«Математическая логика»

Студент

Филатов А.А.

^подпись, дата

^фамилия, инициалы

Группа

АС-09-1

Принял

Гаев Л.В.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

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

1) Доказать принадлежность к NP класcу выбранной задачи.

2) Доказать NP полноту выбранной задачи.

18. РАЗБИЕНИЕ НА ПОДМАТРИЦЫ СО СВОЙСТВОМ СВЯЗНОСТИ

УСЛОВИЕ. Задана (0 - 1) - матрица А порядка m * n.

ВОПРОС. Можно ли так разбить строки матрицы на две подгруппы, чтобы получившиеся в результате матрицы порядков m1 * n и m2 * n (m1 + m2 = m) обладали свойством связности единиц?

2.Доказательство принадлежности к NP классу

Представим условие данной задачи в виде входной цепочки недетерминированной машины Тьюринга:

I: ((a₁₁,a₁₂, … ,a_1n)...(a_m1,a_m2,...,a_mn)).

Цепочку для проверки можно представить в виде:

S: ((a^'₁₁,a^'₁₂, … ,a^'_1n)...(a^'_m11,a^'_m12,...,a^'_m1n)),

((a^''₁₁,a^''₁₂, … ,a^''_1n)...(a^''_m21,a^''_m22,...,a^''_m2n)),

((a^'''₁₁,a^'''₁₂, … ,a^'''_1n)...(a^'''_m11,a^'''_m12,...,a^'''_m1n)),

((a^''''₁₁,a^''''₁₂, … ,a^''''_1n)...(a^''''_m21,a^''''_m22,...,a^''''_m2n)).

Описание выходной цепочки S:

a^’_ij, a^’’_ij - две матрицы, полученные из матрицы a разбиением оной на две подгруппы.

a^’’’_ij, a^’’’’_ij - две матрицы, полученные из матриц a^’_ij, a^’’_ij соответственно, путем такой перестановки столбцов, что в каждой строке все единицы идут подряд. Причем для любого j существует такой k, что для ˅a^’_ij есть a^’’’_ik, и для ˅a^’’_ij есть a^’’’’_ik.

Алгоритм проверки цепочки S:

1) Подсчет элементов a_ij в цепочке I. Временная сложность (m*n).

2) Подсчет элементов a'_ij в цепочке S. Временная сложность (m₁*n).

3) Подсчет элементов a''_ij в цепочке S. Временная сложность (m₂*n).

4) Проверка того, что число элементов во входной цепочке I совпадает с числом элементов в цепочке S, т.е. n*m=n*m₁+n*m₂, или

m=m₁+m₂. Временная сложность (1).

5) Проверка того, что каждая строка матрицы a^’_ij присутствует в матрице входной цепочки а. Временная сложность (m1*n*m).

6) Проверка того, что каждая строка матрицы a^’’_ij присутствует в матрице входной цепочки а. Временная сложность (m2*n*m).

7) Проверка правильности перестановки столбцов. Поиск столбца матрицы a^''' в матрице a^'. Временная сложность (m1*n).

8) Проверка правильности перестановки столбцов. Поиск столбца матрицы a^'''' в матрице a^''. Временная сложность (m2*n).

5) Проверка строк матриц цепочки S на то, что в каждой строке единицы следуют подряд. Временная сложность (m*n).

Полученное время: m*n+m1*n+m2*n+1+m1*n*m+m2*n*m+m1*n+m2*n+m*n = (c учетом условия m1+m2=m) = n*m²+4m*n+1

Таким образом, проверка цепочки S будет проходить за полиномиальное время: n*m²+4m*n+1, то есть понадобится время порядка n*m². Значит проверка цепочки недетерминированной машины Тьюринга пройдет за полиномиальное время порядка m*n, что подтверждает принадлежность данной задачи к NP классу.

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

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

В качестве данной задачи П’ будет выступать задача ГАМИЛЬТОНОВ ПУТЬ .

ГАМИЛЬТОНОВ ПУТЬ

Условие. Дан граф G=(V, E).

Вопрос. Верно ли, что G содержит гамильтонов путь, т. е. такую последовательность <v₁, v₂, ..., v_n> вершин графа G, что n=|V| и (v_i, v_i+1)ε E для всех i, 1≤ i ≤ n.

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

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

Наложим ограничение на условие задачи: пусть m₁=m. То есть вопрос о том, обладает ли исходная матрица связностью единиц.

Тогда необходимо по имеющейся матрице построить двуцветный граф по следующему алгоритму:

1. Каждой строке матрицы А соответствуют черные вершины графа;

2. Каждому столбцу матрицы А соответствуют белые вершины графа;

3. Ребро между вершинами существует тогда и только тогда, если на пересечении соответствующей строки и столбца стоит «1».См. Рис. 1.

Существует доказанная теорема, что если в таком графе есть гамильтонов путь, то матрица обладает свойством связности единиц.

Процесс построения графа имеет полиномиальную временную сложность (m*n+m+n)

Имеем, что задача РАЗБИЕНИЕ НА ПОДМАТРИЦЫ СО СВОЙСТВОМ СВЯЗНОСТИ является частным случаем задачи ГАМИЛЬТОНОВ ПУТЬ при ограничении, что m1=m. Поэтому задача РАЗБИЕНИЕ НА ПОДМАТРИЦЫ СО СВОЙСТВОМ СВЯЗНОСТИ принадлежит к классу NP.

Рис.1 Двуцветный граф