- •Математическая логика
- •Раздел I. Алгебра высказываний
- •1. Высказывания и операции над ними. Формулы
- •2. Следование, эквивалентность и преобразование формул
- •3. Использование законов логики в доказательстве теорем и построении схем
- •Преобразуем эту формулу, используя соответствующие эквивалентности u
- •4. Булевы функции
- •5. Нормальные формы
- •5. Полные системы операций. Алгебра Жегалкина
- •6. Выводимость
- •Раздел II. Алгебра предикатов
- •1. Предикат. Операции над предикатами.
- •2. Модель. Формула алгебры предикатов сигнатуры .
- •3. Формулы алгебры предикатов
- •Основные общезначимости алгебры предикатов
- •Раздел 3. Логические исчисления
- •1. Определение формального исчисления
- •2. Исчисление высказываний ив.
- •3. Отношение эквивалентности в ив
- •4. Исчисление секвенций ис.
- •Исчисления предикатов ип (ипс).
- •Прикладные исчисления предикатов.
- •Автоматическое доказательство теорем
- •Теория алгоритмов
- •Машины Тьюринга
- •2. Рекурсивные функции
- •3. Временная сложность алгоритма. Классы p и np.
- •4. Полиномиальная сводимость. Np-полные языки и задачи.
4. Полиномиальная сводимость. Np-полные языки и задачи.
Какова связь между определёнными выше классами задач P и NP? Очевидно, что (стадия угадывания отсутствует). Естественным кажется предположить, что включение является строгим, однако это утверждение в настоящее время не доказано. Самым сильным доказанным фактом является утверждение
Теорема 4.1. Если , то существует полином, что может быть решена детерминированным алгоритмом с временной сложностью .
Поэтому все утверждения в теории NP-полных задач формулируются, исходя из предположения, что . Цель теорииNP-полных задач заключается в доказательстве более слабых результатов вида: «Если , то». Данный условный подход основывается на понятии полиномиальной сводимости.
Определение. Язык полиномиально сводится к языку, что обозначается, если существует функция, удовлетворяющая условиям:
Существует ДМТ-программа M, вычисляющая f с временной сложностью, ограниченной полиномом, т.е. при некоторомk;
Для любого в том и только том случае, если.
Пусть – задачи распознавания, а– их схемы кодирования, то задача1 полиномиально сводится к задаче 2 (обозначается ), если.
Например, задача существования гамильтонова цикла полиномиально сводится к задаче коммивояжера. Для сведения задачи достаточно положить , если, и, в противном случае. ГраницаB для длины искомого пути берётся равной , где.
Рассмотрим свойства полиномиальной сводимости.
Лемма 1. Если , то изследует, что.
Доказательство. Пусть – алфавиты языковсоответственно. Так как, то существует отображение. Обозначим через:
–полиномиальную ДМТ-программу, реализующую это отображение;
–программу распознавания языка ;
–программу распознавания языка .
Программа распознавания языка может быть построена как композиция программи. Ко входуприменяется программа, которая строит, затем кприменяется программа, определяющая верно ли, что. Так как , то эта программа является программой распознавания языка.
Оценим временную сложность этой программы. Так как , то. Если, то. Тогда==, где. Следовательно,. Лемма доказана.
Лемма 2. Если и, то.
Доказательство аналогично, выполнить самостоятельно.
Определение. Язык L называется NP-полным, если и любой другой языкполиномиально сводится кL ().
Аналогично определяются NP-полные задачи.
Лемма 3. Если ,являетсяNP-полным и , тоявляетсяNP-полным.
Доказательство. Так как , то достаточно показать, что для любого языкасправедливо. ЯзыкявляетсяNP-полным, а, следовательно, . По условию, поэтому, в силу транзитивности отношения (лемма 2) получим .
Лемма 3 даёт рецепт доказательства NP-полноты задачи , для этого нужно показать, что:
;
NP-полная задача полиномиально сводится к.
Для того чтобы доказывать NP-полноту с помощью полиномиальной сводимости нужно доказать существование хотя бы одной NP-полной задачи. Это сделал в 1971 году С. Кук, а такой задачей явилась задача “выполнимость”.
Задача “выполнимость”. Задано множество логических переменных и составленный из них набор элементарных дизъюнкцийC. Существует ли набор значений множества X, на котором истинны все дизъюнкции множества С?
Эквивалентная формулировка данной задачи: “Является ли выполнимой формула, равная конъюнкции всех элементарных дизъюнкций множества С над множеством высказывательных переменных X?”
Теорема 4.2.(Кука) Задача “выполнимость” является NP-полной.
Рассмотрим основную идею доказательства теоремы. Покажем, что произвольную задачу из NP можно свести к задаче выполнимость за полиномиальное время.
Так как , то существует НДМТ-программаM её распознавания с полиномиальным временем работы. Построим группы дизъюнкций, описывающие работу программы M и принимающие значения 1 тогда и только тогда, когда программа M принимает входное слово .
Пусть , так как, то число шагов МТ-программы ограничивается числом, а номера ячеек ограничены интервалом.
Обозначим:
t – момент времени (номер шага программы) ;
k – номер состояния машины , где,;
j – номер просматриваемой ячейки ;
l – номер символа алфавита , где.
При построении дизъюнкций будут использоваться предикаты:
–в момент времени t программа находится в состоянии ;
–в момент времени t головка просматривает ячейку j;
–в момент времени t в ячейке j находится символ .
При фиксированных значениях предметных переменных они являются высказываниями и могут трактоваться как высказывательные переменные, принимающие различные значения в зависимости от значений параметров.
Выпишем теперь требуемые группы дизъюнкций и оценим количество дизъюнкций в каждой группе.
Группа дизъюнкций описывает конфигурацию программы в начальный момент времениt0:
–в момент времени 0 программа находится в состоянии q0;
–в момент времени 0 головка просматривает 1-ю ячейку;
–в момент времени 0 в 0-й ячейке находится символ b;
, , , – в момент времени 0 в ячейках с номерами с 1-й поn-ю записано входное слово x;
, , , – в момент времени 0 ячейки с номерами сn+1 по пусты.
Общее число этих дизъюнкций равно .
Группа содержит утверждения: “В каждый моментt программа M находится только в одном состоянии”. Они записываются следующими дизъюнкциями:
, ;
, .
Число таких дизъюнкций равно .
Группа содержит утверждения: “В каждый моментt головка просматривает только одну ячейку”. Аналогично получим:
, :
, .
Количество дизъюнкций группы равно .
Группа содержит утверждения: “В каждый моментt каждая ячейка содержит только один символ алфавита :
, ,;
, .
Количество дизъюнкций группы равно .
Группа описывает переход машинной конфигурации в следующую, согласно функции переходов (). Введём вспомогательную переменную, выражающую конфигурацию программы в моментt, где ,,. Тогда переход в следующую конфигурацию представляется набором дизъюнкций:
(представление в виде ДНФ высказывания );
();
().
Общее число этих дизъюнкций равно .
Кроме того, если в момент t ячейка j не просматривается, то её содержимое не меняется. Это описывается высказыванием , которое эквивалентно дизъюнкции
.
Количество дизъюнкций d) равно .
Группа , отражающая утверждение “Не позднее, чем черезшагов программа перейдёт в состояниеqY”, состоит из единственного высказывания .
Таким образом, если , то у программыM есть на входе x принимающее вычисление длины не более , и это вычисление даёт при заданной интерпретации переменных набор значений истинности, который выполняет все дизъюнкции из. И наоборот, набор дизъюнкцийС построен так, что любой выполняющий набор истинности для С должен соответствовать некоторому принимающему вычислению программы M на входе x.
Осталось показать, что для любого фиксированного языка L индивидуальная задача “выполнимость” может быть построена за время ограниченное полиномом от. В качестве функции длины для задачи “выполнимость” можно взять . Так каки, то. Следовательно, задача “выполнимость” является NP-полной.