4.9. Несколько доказательств эквивалентности задач

В настоящее время получено доказательство эквивалентности обширного семейства задач. Сводимость задач, о которых вначале было известно, что они принадлежат классу к задаче Кука была доказана либо непосредственно, либо косвенно (с помощью транзитивности) с использованием дерева, изображенного на рис. 4.10.

Чтобы доказать, что задача является -полной, мы каждый раз должны доказывать, что:

• Q попадает в класс NP;

• Q является -сложной.

Однако, поскольку доказал, что для всякого сводится к задаче разрешимости логического выражения, остается доказать, что логическая разрешимость сводится к

Рис. 4.10. Доказанные отношения сводимости в классе -полных задач.

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

Сначала докажем, что задача разрешимости логического выражения — даже гораздо более простого по форме, чем общий случай, рассматриваемый в теореме Кука, — является тем не менее эквивалентной задаче в общем виде.

Пример 1

• Задача разрешимости логического выражения, приведенного к нормальной конъюнктивной форме (НКФ), является -полной.

• Задача разрешимости логического выражения, приведенного к НКФ и имеющего не более трех литералов в одном операторе, является -полной.

Некоторое выражение является приведенным к НКФ, если оно записывается как логическое произведение (операция А) сумм (операция V) элементарных единиц, называемых

литералами; каждый литерал — это либо либо , где обозначает логическую переменную. Выражение из условия Н в доказательстве теоремы Кука может быть приведено к НКФ. В самом деле, если перейти от переменных, принимающих значение и I, к логическим то суммы

могут быть записаны в виде

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

Таким образом, условия А, В и С приводимы к Стандартизация условия достигается благодаря тому, что во всех случаях осуществляется замена символа заменяется на т. е. на выражение, приведенное к НКФ, общая длина которого а в худшем случае удваивается. Условия приводятся к НКФ с помощью замены типа переменных — с булевых на логические

Итак, длина выражения Я была умножена на константу, и поэтому результат Кука сохраняет свою значимость и для выражений, приведенных к Следовательно, в дальнейшем мы можем ограничиться рассмотрением множества выражений, приведенных к

Среди них первыми очевидными кандидатами в задачи класса NP являются выражения, содержащие не более трех литералов в одном операторе (так называемые -НКФ»).

1. Задача о разрешимости 3-НКФ попадает в класс потому что очевидно, что для НДМТ можно установить некоторый алгоритм, число этапов в котором постоянно и равно 3:

(см. скан)

2. Задача разрешимости произвольного логического выражения сводится к задаче разрешимости -НКФ.

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

Как можно легко доказать индукцией по эти два выражения формально эквивалентны.

Пусть имеется некоторое решение выражения, записанного в иксах, например Зададим теперь

Тогда выражение, записанное в иксах и игреках, тоже имеет значение ИСТИНА.

Наоборот, если существует множество значений придающих этому выражению значение ИСТИНА, значение по крайней мере одного должно быть ИСТИНА, так как значение первого оператора непременно ИСТИНА. Следовательно, мы получаем

(см. скан)

Так, например, при и указанном преобразовании выражение приобретает вид причем оба выражения эквивалентны.

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

Итак, мы можем задачу разрешимости произвольного логического выражения свести за полиномиальное время к задаче разрешимости -НКФ.

Пример 2. Задача существования К-клики на произвольном графе является -полной.

{Клика — подмножество попарно связанных вершин; К-клика — клика мощностью К}

1. Эта задача принадлежит классу поскольку каким бы ни был граф, существует (т. е. полиномиальное число) подмножеств, состоящих из К вершин. В каждом из них достаточно проверить существование ребра между двумя произвольными вершинами. Следовательно, нужно выполнить тестов.

2. Задача разрешимости сводится к задаче существования -клики.

Пусть даио произвольное выражение Е, приведенное к НКФ и содержащее К операторов:

где переменная или ее отрицание.

В соответствии с этим выражением построим граф, каждая вершина которого соответствует паре где х является литералом оператора С, из выражения Е, и дуга которого связывает тогда и только тогда, когда

т. е. этим двум вершинам соответствуют различные операторы;

т. е. эти два литерала не являются отрицанием друг друга.

Перед тем как продолжить доказательство, изобразим пример такого графа. Если выражение Е имеет вид

результирующий граф имеет девять вершин — столько же, сколько литералов содержится в Е. Ребро связывает два литерала, входящие в различные операторы, причем значение этих литералов может быть одновременно ИСТИНА (рис. 4.11).

Существование в этом графе -клики соответствует, следовательно, случаю, когда для выражения Е существует множество из К литералов, принадлежащих К различным операторам

Рис. 4.11. Окончательный граф для задачи о К-клике.

(т. е. в данном случае всем) и способных одновременно принимать значение ИСТИНА.

И наоборот, если выражение разрешимо, т. е. если для переменных существует множество истинностных значений, таких, что каждый оператор принимает значение ИСТИНА, то в каждом из К операторов существует по крайней мере один литерал, имеющий значение ИСТИНА. По построению этому множеству литералов в нашем графе соответствует множество из К принадлежащих к разным операторам и взаимно не исключающих друг друга — а в силу этого связанных друг с другом — вершин, т. е. -клика.

В рассматриваемом случае и мы получаем клику или же клику поскольку присутствует всегда.

Пример 3. Задача о существовании решения системы уравнения в целых числах является -полной.

1. Эта задача относится к классу поскольку она может включать лишь конечное число различных выборов (число значений переменных).

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

Действительно, построим вида булевыми неизвестными находящимися во взаимно однозначном соответствии с неизвестными из исходного выражения в в Е) с К условиями, если Е содержит К операторов; Пусть для элементов из

Отсюда следует, что условию, накладываемому на соответствует оператор, если в качестве второго члена этого условия мы возьмем

Очевидно, что С будет удовлетворено в том и только в том случае, когда по крайней мере один «положительный» литерал (соответствующий значению имеет значение ИСТИНА или когда по крайней мере один «отрицательный» литерал (т. е. ) имеет значение ЛОЖЬ.

Это двойное условие записывается также в

где — литерал из — литерал из

В соответствии с определением последнее неравенство можно также записать следующим образом:

Следовательно, если E удовлетворено, то по крайней мере один из равен 1 или же один равен 0 для любого . В самом деле, если где входит в то справедливо выражение (1), поскольку во всех случаях у

В другом случае, когда где входит в это предполагает в первую очередь, что так как сумма для является положительной, неравенство (1) выполнено, поскольку

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

В частности, для того же выражения Е, которое рассматривалось выше при установлении отношения эквивалентности классов задач определяемая выше система уравнений в целых числах имеет вид

Очевидное решение этой (из-за ) является Сумма в этом случае дает — — условие, из которого при объединении с получаем

После этого имеем

Отсюда в зависимости от значения мы получаем два решения:

Очевидно, что они могут быть в свою очередь поставлены в соответствие двум кликам мощностью 4 из предыдущей задачи.