Теорема Кука (NP-полнота задачи «ВЫП»)

Теорема 4 «Теорема Кука»

Задачи проверки выполнимости произвольной логической функции в конъюнктивной нормальной форме является

Доказательство:

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

 

Этот факт соответствует набору следующих выражений:

G1: В любой момент времени соответсвующая машина Тьюринга находится в одном и только одном состоянии

G2: В любой момент времени считывающая головка машины может обозревать одну и только одну ячейку

G3: В любой момент времени ячейка в активной зоне может содержать только один символ внутреннего алфавита .

G4: В начальный момент времени «0» машина находится в конфигурации

G5:Не более чем через полиноминальное число шагов машина приходит в состояние

G6:В каждый момент времени конфигурация машины в следующий момент времени определена одной из команд машины НТ.

 

Выполнение утверждений G1-G6 означает, что задача принадлежащая классу имеет ответ «ДА»

 

Теперь эти утверждение нужно представит в виде КНФ

G1: - мощность внутреннего алфавита

- одновременно в двух состояниях находится не может.

Получаем порядка дизъюнкций для каждой из пар Общее количество переменных будет порядка - полиноминальная оценка задачи, где - длина входа.

Таким образом имея задачу удостоверения мы конструируем КНФ и задача удостоверения сводится к проверке выполнимости КНФ.

 

Примеры NP-полных задач:

1. Задача «3ВЫП». Пусть формула от булевых переменных в конъюктивной нормальной форме, где каждая дизъюнкция имеет не более, чем три вхождения переменных. Задача проверки выполнимости таких формул называется задачей 3 – выполнимости («3ВЫП»). Задача «3ВЫП» является NP – полной . Причем формулу с 3-я дизъюнкциями преобразовать в задачу с 2-я дизъюнкциями за полиноминальное число шагов нельзя.

2.

- клика мощности 3

G

Задача «КЛИКА». Рассмотрим графическую задачу: по произвольному графу и числу узнать, имеется ли в графе полный подграф с вершинами (клика). (Граф называется полным, если любые вершины соединены ребром .

3. Задача «вершинное покрытие» (ВП). Говорят, что некоторое множество вершни графа образует вершинное покрытие графа, если для любого ребра найдется идентичная ему вершина этого множества.

4. Задача «независимые вершины» (НВ). Говорят, что множество вершин графа независимо, если никакие две вершины из не связаны ребром. Задача о независимом множестве вершин заключается в том, чтобы для произвольного графа и целого числа выяснить, существует ли в независимое множество из вершин.

5. Задача «Гамильтонов цикл» (ГЦ). Цикл на графе – это замкнутый путь (замкнутая траектория) состоящая из ребер, при котором каждая из вершин не повторяется дважды. Гамильтонов цикл – это цикл, который проходит все вершины. Гамильтонов цикл – это некое упорядочивование вершин. Для произвольного графа требуется узнать, существует ли перестановка вершин , такая, что выполнено: . Задача состоит в том, чтобы выяснить существует ли в графе гамильтонов цикл.

6. Задача о множестве ребер разрезающих цикл РЦ. Множество ребер разрезающих циклы. Для произвольного графа и целого числа выяснить существует ли множество , такое, что и каждый цикл графа содержит ребро из .

7. Задача о множестве вершин разрезающих циклы (ВЦ). Для каждого цикла имеется вершина из этого множества.

8. Задача о изоморфизме подграфу (ИП). Два графа называются изоморфным, если существует отображение одного графа на другой, при котором вершины одного графа переходят в вершины другого графа: . Задача: для заданных двух графов и выяснить, содержит ли граф подграф, изоморфный .

9. Задача целочисленный рюкзак (ЦР). Для произвольных чисел и требуется узнать существует ли набор целых чисел , что выполнено . Вариантом задачи является - рюкзак, в которой требуется установить существование - чисел с условием .

10. Проблема разрешимости диофантовых уравнений 2-ой степени. Вопрос: разрешимо ли в целых числах?

 

11.

k

…

Задача целочисленный рюкзак в виде графа. Имеем вершину. Соединяем их ребрами следующим образом: если , то соединяем.

Рассмотрим следующий случай если :

 

Построить граф можем за шагов, где -количество входных чисел - размерность задачи)

Число может быть представлено в виде суммы , если в графе существует путь по ребрам из нулевой вершины в -ую.

Если пути нет, то не представимо в виде суммы .

Построим пут по шагам:

Шаг 0: находимся в вершине 0

Шаг 1: метим все вершины меткой «1», которые можем достичь за один шаг (соединены с вершиной 0 ребром)

Шаг 2: для каждой из вершин с меткой «1» находим вершины, которые могут быть достигнуты из вершин с меткой «1» за один шаг и отмечаем их меткой «2» и т. д.

Эта процедура требует порядка действий. Если в рамках данной процедуры пометим число , то такой путь существует, иначе пути нет.

Если не достижимо, то действий будет - вершин и ребер. Если набор ребер упорядочен, то будет действий, чтобы пометить все вершины.

Сложность это алгоритма - трудоемкость построения самого графа.

Нашли ли полиноминальный алгоритм для решения - полной задачи? Другими словами, является ли оценка полиноминальной?

 

…

…

…

, где - набор входных параметров ( и , - максимальный из них), - средний размер для кодировки одного параметра.

Значения, которые мы кодируем определяются пропорционально и зависят от основного машинного алфавита. В ячейках для двоичной системы кодирования .. В ячейках для десятичной системы кодирования . Оценка не является полиноминальной. т. к. при любой кодировке кроме унарной зависимость размера задачи от входа экспоненциальная.

Такие алгоритмы выделяю в отдельный класс – псевдополиноминальные.

 

Рассмотрим проблему . В ней выделим подпроблему , где - произвольная функция от параметров задачи:

Под будем понимать такие задачи, в которых максимальный параметр ограничен

Задача является сильно полной, если существует некоторый полином для которого подзадача является

 

Сильная NP-полнота

 

Теорема 5 «О сильной полноте»

Если , то никакая сильная задача не имеет псевдополиноминального алгоритма решения.

Доказательство:

Пусть - сильная задача и существует алгоритм решения проблемы : . По определению сильной задачи: , для которого существует подзадача для проблемы алгоритм разрешения имеет полиноминальную сложность , что противоречит исходному предположению «такого алгоритма не существует» (