9.2.3.Сводимость по Тьюрингу

Это иной подход к понятию сводимости. Заметим, что в оригинальной работе Кука использовался именно он.

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

В задачах оптимизации Z для каждого входа I условия задачи определяют множество конечных объектов S_Z(I), которые являются ее решениями. Так, в задаче "гамильтонов цикл" это некоторый гамильтонов цикл, а в задаче "коммивояжер" на минимум - это гамильтонов цикл минимального веса. Первая из этих задач является задачей в форме распознавания, а вторая таковой не является. Но даже при решении первой как задачи в форме распознавания ответом будет только утверждение о наличии или отсутствии гамильтонова цикла, в то время как ее же решение в оптимизационной форме предполагает в качестве ответа предъявление требуемого гамильтонова цикла в случае его наличия.

Считается, что некоторый алгоритм решает задачу Z, если он выдает некоторый sS_Z(I), если множество S_Z(I) не пусто. В противном случае он выдает некоторый условленный ответ, например, "нет".

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

Пусть имеется алфавит A. Обозначим через A⁺ множество всех непустых слов этого алфавита. Словарным отношением над алфавитом A называется бинарное отношение RA⁺xA⁺.

Со словарным отношением R свяжем язык L над A. Определим некоторое словарное отношение R={(I,s): IA⁺ и IL}. Здесь s- любой фиксированный символ алфавита A.

Говорят, что функция f: A*A*реализует словарное отношение R тогда и только тогда, когда для каждого IA⁺ имеет месть f(I)=, если не существует yA⁺ такого, что(I,y)R; в противном случае f(I)=y для некоторого yA⁺, (I,y)R.

МТ разрешает отношение R, если она вычисляет функцию f, которая реализует R.

Если раньше речь шла только о кодировании условия задачи Z, то теперь схема кодирования включает как кодирование входа I, так и кодирование решения S_Z(I). Тогда задаче Z можно сопоставить словарное отношение R={(x,y)}, где x - код входа индивидуальной задачи, а y -код некоторого ее решения. (Как и раньше, чтобы не загромождать изложение мы не будем различать сам вход и его код.)

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

Определение. Пусть R и R' - два словарных отношения над A. Будем говорить, что R сводится по Тьюрингу к R', если существует оракульная машина Тьюринга M с входным алфавитом A такая, что для любой функции g:A*A*, реализующей словарное отношение R', релятивизированная программа M_g будет полиномиальной программой ОМТ, а функция, вычисляемая программой M_g, будет реализовывать отношение R.

Обозначим этот тип сводимости как R_TR'. Как и в случае полиномиальной сводимости имеет место транзитивность.

Лемма. Если L₁_TL₂ и L₂_TL₃, то L₁_TL₃.

Данное понятие сводимости относится уже не только к задача в форме распознавания, т.е. оно является более широким и, возможно, позволяет анализировать сложность задач за пределами класса NP задачи.

Словарное отношение R назовем NP-трудным, если существует NP-полный язык L (представленный как словарное отношение), который сводится по Тьюрингу к R, т.е. L_TR. Более неформально NP-трудная задача определяется как задача, к которой по Тьюрингу сводится некоторая NP-полная задача.

Пример. Задача "разбиение" сводится по Тьюрингу к задаче "K-е по порядку подмножество".

Первая определена выше. Вторая задача состоит в следующем. Задано конечное множество A, каждый его элемент a имеет размер s(a), выраженный натуральным числом. Заданы также два неотрицательных числа K2^|A| и

Вопрос заключается в следующем. Существует ли не менее K различных подмножеств A'A, удовлетворяющих условию s(A')B, где

Весьма вероятно, что эта задача не принадлежит классу P. Более того, она может не принадлежать и NP.Интуитивно очевидный путь ее решения на НМТ требует угадывания K подмножеств множества A. Пока неизвестен способ записать эти угаданные подмножества на ленте в виде слова, длина которого была бы полиномом от |A|logKlogs(A). Если говорить о полиномиальной сводимости, то сегодня неизвестно никакой NP-полной задачи, которая бы сводилась к задаче "K-е по порядку подмножество".

Покажем теперь, что задача "разбиение" сводится по Тьюрингу к задаче "K-е по порядку подмножество".

Пусть S(A, s, B, K) - программа для решения задачи "K-е по порядку подмножество". Положим |A|=n. Условие индивидуальной задачи "разбиение" задаются просто в виде множества A с размерами элементов. Программа для решения задачи "разбиение" начинается с вычисления s(A). Если оно нечетно, то ответ "нет". В противном случае полагаем B=s(A)/2 и применяем приведенный ниже алгоритм (он использует процедуру S(A, s, B, K)), позволяющий определить число L* подмножеств A'A, удовлетворяющих условию s(A')B.

1. Шаг 1. Положить L_min=0, L_max=2ⁿ.

2. Шаг 2. Если L_min-L_max=1, то положить L*= L_min и остановиться.

3. Шаг 3. Положить L=(L_min+L_max)/2 и вызвать подпрограмму S(A, s, B, L). Если ответ "да", то положить L_min=Lи перейти к шагу 2. В противном случае положить L_max=L и перейти к шагу 2.

Подпрограмма S(A, s, B, L) вызывается ровно n раз. Требуется еще один вызов S(A,s,B-1,L*) для определения ответа в задаче "разбиение". Если ответ будет "да", то все подмножества A'A, удовлетворяющих условию s(A')B, должны удовлетворять и условию s(A')B-1. Поэтому ответом в задаче "разбиение" будет "нет". В противном случае должно существовать некоторое подмножество A'A, удовлетворяющее условию s(A')=B. Поэтому ответом в задаче "разбиение" будет "да".

Мы видим, что данный тип сводимости, возможно, позволяет выйти за пределы класса NP и оценивать сложность задач, сформулированных не только в виде задач распознавания. Ряд известных оптимизационных задач мы задавали в форме распознавания: задача о коммивояжере, задача ЦЛП, задача о клике и др. В этой форме они принадлежат классу NP и, как мы ниже увидим, являются NP-полными. Их NP-полнота доказывается с использованием полиномиальной сводимости. Если их задавать в традиционной для них оптимизационной форме, то нельзя использовать понятие полиномиальной сводимости. В то же время можно использовать сводимость по Тьюрингу. Ко всем таким задачам можно по Тьюрингу сводить NP-полные задачи. Поэтому оптимизационная форма NP-полной задачи, как правило, является NP-трудной задачей.

Пока отвлечемся от этого и вернемся к NP-полным задачам.