Начальная информация

Рис. 5.1 Расположение информации на ленте

Вычисления при любом допустимом значении объекта у происходят в зоне ленты [-Т, Т] и завершаются не более чем за Т шагов (тактов работы НДМТ). Машина, начав работу в конфигурации , останавливается в конфигурации , если свойство R(x , y) выполнено, и в - в противнем случае. Здесь - начальное, а - заключительное состояние НДМТ. Построим КНФ Ф такую, что любая задача проверки (распознания) свойства (в общем виде: ) полиномиально сводится к проверке выполнимости КНФ

Ф = В & C & D & Е & F & G,

где В, С, D, E, F, G - дизъюнкты, имеющие следующий смысл:

В = 1 На каждом шаге головка машины обозревает ровно одну ячейку ленты.

С = 1 В каждой ячейке на каждом шаге записан в точности один символ.

D = 1 На каждом шаге работы машина находится ровно в одном состоянии.

Е = 1 Начальная конфигурация машины имеет вид .

F = 1 Машина работает по тьюринговской программе.

G = 1 Заключительная конфигурация машины имеет вид , если Р(х,у) = 1.

Обозначим , - внешний и внутренний алфавиты НМДТ; t – произвольный шаг выполнения алгоритма, ; s – текущий номер ячейки, ; i и j - текущие номера символов алфавитов А и Q, , .

Введем по определению следующие логические переменные:

, если на шаге t, обозревая ячейку s, машина воспринимает символ с номером i, иначе эта переменная равна нулю.

, если на шаге t машина находится в состоянии с номером j , иначе эта переменная равна нулю.

, если на шаге t головка машины обозревает ячейку с номером s, иначе эта переменная равна нулю.

Используя введенные логические переменные, можно записать в виде формул следующие логические условия.

;

на шаге t машина обозревает хотя бы одну ячейку и при этом никакие две ячейки одновременно, т. к. . Тогда

.

;

на шаге t в ячейке s записан ровно один символ. Тогда

.

;

на шаге t машина находится ровно в одном состоянии. Тогда

.

В начальном положении (t=0) головка машины обозревает ячейку с номером 1 в состоянии q₁, а в первых n - ячейках записаны символы слова Х = х(1)...х(n), за ним - разделительный знак «*», после чего - слово Y=y(1)...y(q) и далее - пустые ячейки. Выполнение такой начальной конфигурации равносильно Е = 1 , где

;

,

где  - пустой символ, а запись означает индекс символа в ленточном алфавите.

Полиномиальная программа проверки свойства состоит из тьюринговских команд:

.

Здесь - функция смены состояний нмт, - функция, определяющая записываемый на ленту символ, - функция, определяющая движение головки машины, . Введем вспомогательную функцию –

Пусть по определению , если на шаге t, находясь в состояний , машина обозревает ячейку с номером s, в которой записан символ , и смена состояния и записи в ячейке осуществляется в соответствии с программой, причем при отсутствии головки над ячейкой s запись в этой ячейке не изменяется; в противном случае .

.

.

,

где выражение в квадратных скобках соответствует тому, что на последнем шаге Т на ленте записаны символы (пусто) и 1, причем единица содержится не более чем в одной ячейке; сомножитель соответствует нахождению машины на шаге Т в состоянии ; последняя конъюнкция обеспечивает условие наличия в обозреваемой ячейке символа 1.

Приведенные выше выражения позволяют заключить, что формула Ф = В & C & D & Е & F & G будет являться КНФ, если привести промежуточные эквивалентные преобразования:

.

Условие Ф = 1 равносильно тому, что найдется такое допустимое значение у, при котором машина, начав работу в конфигурации перейдёт в конфигурацию согласно тьюринговской программе полиномиальной проверки.

Если задача z имеет положительный ответ, то для некоторого допустимого у выполнено R(x,y)=1. В этом случае, назначив значения переменных на основе работы машины над начальной конфигурацией , получим набор, на котором Ф=1. Обратно, если существует набор, обращающий Ф в единицу, то значения переменных в этом наборе определяют слово у , такое, что машина переводит в . Следовательно, задача z сведена к задаче выполнимости КНФ.

Очевидно, что длина записи формулы Ф при любом способе ее представления в виде слова над конечным алфавитом ограничена некоторым полиномом от размера входа задачи, и сведение задачи z к задаче осуществимо за полиномиальное время.

Теорема полностью доказана.

2) Класс NPC – универсальных переборных задач и приемы доказательства NP-полноты [1,2,3,4,5,6,7,8,9]

Пусть Г =(Х,U) - конечный граф, Х - множество вершин графа, U - множество ребер. Не теряя общности, можно обозначить вершины натуральными числами: Х = {1,2,..., n}, а ребра задать булевой матрицей такой, что , если ребро ( i,j) имеется в графе Г, и , если ребра ( i,j) в графе Г нет. Граф называют полным, если любые его две вершины соединены ребром. Граф называют подграфом графа Г, если и .

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

Теорема 7.1. Задача о полном подграфе является NP- полной.

Доказательство. Для удобства обозначим задачу о полном подграфе . Начальной информацией о задаче является число и матрица а) Докажем, что  NP. Для этого выписываем N- программу:

УСПЕХ := TRUE; //Предположим, k-полный подграф существует

// Недетерминированный выбор k вершин

Set := [1..n];

for i := 1 to k dо

begin

node:= CHOOSE(Sеt);

v[i]:= node;

Set:=Set\(nodе)

еnd;

// Полиномиальная проверка

for i := 1 tо k-1 do

for j := i+1 tо k dо

if u(v[i] ,v[j])=0 then УСПЕХ:=FALSE;

write(УСПЕХ);

Очевидно, что сложность приведенной N-программы может быть оценена как О(n(n-1 )/2), т.е. полиномиально, откуда следует, что  NP.

б) Докажем, что  . Поскольку ранее мы убедились, что - NP-полная задача, то из полиномиальной сводимости  будет следовать полиномиальная сводимость любой задачи класса NP к .

Пусть

есть произвольная k скобочная КНФ. Поставим во взаимно-однозначное соответствие каждому литералу из Ф вершину некоторого графа Г. Этот граф будет содержать вершин. Пометим для удобства каждую вершину соответствующим ей литералом и порядковым номером скобки, в которую этот литерал входит, т.е. парой

Соединим дугой те и только те пары полученных вершин и , для которых одновременно выполняются два условия:

а) (литералы принадлежат разным скобкам);

б) (один литерал не является отрицанием другого).

Таким образом, построен граф Г =(X,U) с указанными вершинами и ребрами. Предположим, - что Ф – выполнима, и -набор, на котором . Тогда в каждом наборе КНФ Ф найдется хотя бы один литерал, обращающийся в единицу. Выберем произвольно по одному такому (обращающемуся в единицу) литералу из каждой скобки. Будет выбрано ровно k литералов. Рассмотрим соответствующие именно этим литералам k вершин графа Г и убедимся, что любая пара из них соединена ребром. Действительно, пометки этих вершин удовлетворяют условиям а) и б), т.к. литералы принадлежат разным скобкам и одновременно принимают единичное значение, поэтому один из них не может быть инверсией другого.

Обратно, пусть граф Г содержит полный подграф с k вершинами . зададим переменным с номерами значения: , а остальные переменные, если k < n , зададим произвольно, получая набор . Тогда Поскольку эти литералы соответствуют вершинам полного подграфа, то они относятся к разным скобкам КНФ Ф , откуда следует, что . По построению графа Г очевидно, что преобразование задачи выполнимости КНФ в задачу может быть осуществлено с полиномиальной сложностью.

Теорема доказана.

Литература:

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. – 416 с.

2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.

3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.

4. Донской В. И. Дискретная математика. –Симферополь: Сонат, 2000. –356 с.

5. Липский В. Комбинаторика для программистов. М.: Мир, 1988. – 215 с.

6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995. – 256 с

7. Линдон Р. Заметки по логике. М.: Мир, 1968. – 128 с.

8. Оре О. Теория графов. М.: Наука, 1980. – 336 с.

9. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. – 400 с.