Задачи разновидности языка и кодирование

Из соображения удобства теория NP – полных задач строится только для задач распознавания свойств. Такие задачи имеют только два возможных решения: “да” и “нет”. Формально, задачи распознавания П состоят из двух множеств: 1) множество D_П всех возможных индивидуальных задач; 2) Множество индивидуальных задач с ответом “да”. Стандартная форма, которую мы будем применять для описания задач, состоит из двух частей: в первой части даётся описание условия задачи в терминах различных компонентов, во второй части формулируется вопрос-предположение, предполагающий один из двух ответов “да” или “нет”. Это описание определяет множествоD_П и Y_П. Индивидуальная задача принадлежит множеству D_П в том случае, когда она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условий индивидуальных задач, множеству Y_П в том случае, когда ответом на вопрос задачи будет “да”.

Примеры массовых задач пример 1.”Изоморфизм подграфу”

Условие:

Даны 2 графа G₁ = (V₁,E₁) и G₂ = (V₂,E₂).

Верно ли, что G₁ содержит подграф, изоморфный G₂? Другими словами, существует ли:

1) Подмножества ,такие, что,.

2) Взаимнооднозначная функция f, отображающая , такая, что ребросуществует тогда и только тогда, когда существует ребро.

ПРИМЕР 2.”Коммивояжер”

Условие:

Заданы конечное множество городов C={C₁, C₂, … , C_n}, расстояния d(C_i, C_j) и граница B, являющаяся натуральным числом.

Существует ли замкнутый маршрут, проходящий через все города из C, длина которого не превосходит B, т.е. существует ли последовательность <C_π(1), C_π(2),…, C_π(n)> такая, что ?

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

Лекция 4

Теория NP – полных задач ограничивается только задачами распознавания. Это объясняется тем, что задача распознавания имеет естественный формальный эквивалент, удобный для изучения методами теории вычислений. Этот эквивалент называется языком и определяется следующим образом. Для любого конечного множества символов , называемого алфавитом, и– множества всех конечных цепочек, любое подмножествоназывается языком в алфавите. Соответствие между языком и задачами распознавания устанавливается с помощью схем кодирования. Схема кодированияe задачи П описывает каждую индивидуальную задачу из П подходящим словом в некотором фиксированном алфавите . Таким образом, задачаП, схема кодирования e задачи П разбивают слова из на три класса:

1) Слова не являются кодами индивидуальной задачи из П.

2) Слова являются кодами индивидуальной задачи из П с отрицательным ответом на вопрос.

3) Слова являются кодами индивидуальной задачи из П с положительным ответом на вопрос.

Третий класс слов является тем языком, который ставится в соответствие задаче П при схеме кодирования е и обозначается ={:x - код индивидуальной задачи I из множества Y_П со схемой кодирования e}.

При применении формальной теории NP – полноты к задачам распознавания, будем говорить, что некоторый результат имеет место для задачи П при схеме кодирования e, если результат имеет место для языка . Еслие и е’ – любые две разумные схемы кодирования для задачи П, то рассматриваемое свойство языков ивыполняется или не выполняется одновременно, это позволяет не указывать явно схемы кодирования, т.е. мы можем неформально говорить, что рассматриваемое свойство для задачиП выполняется или не выполняется.

Будем считать, что с каждой задачей распознавания связана независящая от схемы кодирования функция Length, которая отображает D_ПN – это функция полиномиально эквивалентна длине кода индивидуальной задачи, полученной при любой разумной кодировке. Полиномиальная эквивалентность понимается в следующем смысле: для любой разумной схемы кодирования e задачи П существуют два полинома p и p’ такие, что для любой индивидуальной задачи I из D_П, если x – длина её кода, то Length(I)<p(x) и x<p’(Length(I)).

Например, в задаче ИЗОМОРФИЗМ ПОДГРАФУ можно положить Length(I)=|V₁|+|V₂|, где G₁=(V₁,E₁) и G₂=(V₂,E₂) – графы, образующие индивидуальные задачи.

В задаче О КОММИВОЯЖЁРЕ можно определить функцию

Length(I)=n++max(log d(C_i, C_j) :).

Здесь b понимается как наименьшее целое число, большее или равное аргументу b.

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

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

Детерминированные машины Тьюринга и класс P

Для того чтобы формализовать понятие алгоритма, необходимо зафиксировать определённую модель процессов вычислений. Такой моделью у нас будет служить детерминированная одноленточная машина Тьюринга (ДМТ). От рассмотренной нами ранее МТ данная модель отличается тем, что машина может завершить свою работу, только оказавшись в одном из двух состояний q_Y или q_N.

В первом случае считается, что результатом работы ДМТ будет ответ “да”, а во втором – ответ “нет”.

Соответствие между распознаванием языков и решением задач распознавания определяется следующим образом. Будем говорить, что ДМТ программа M решает задачу распознавания П при кодировании e, если M останавливается на всех словах, составленных из букв входного алфавита и L_M=.

Определим понятие «временная сложность». Время, требуемое ДМТ с программой М, для вычисления при входе x, есть число шагов, выполняемых до момента остановки. Если программа M останавливается на всех входах x из , то временную сложностьT_M этой программы можно определить как функцию :

T_M(n)=max{m: существует такое слово , имеющее длину |x|=n, что вычисление программой M при входе x требует время m}.

Детерминированная программа M называется полиномиальной ДМТ программой, если существует такой полином p, что для всех ,T_M(n)≤p(n). Теперь формально можно определить класс языков P. P = {L: существует полиномиальная ДМТ программа M такая, что L=L_M}. Определение означает, что задача распознавания , при кодированииe, если , т.е. существует полиномиальная ДМТ программа, которая решает задачуП при кодировании e. Учитывая рассуждения об эквивалентности разумных кодировок, мы обычно не будем приводить конкретные схемы кодирования, а будем просто говорить, что задача распознавания .

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

Недетерминированное вычисление и класс NP

Сначала поясним смысл понятия, лежащего в основе определения класса NP.

Рассмотрим задачу КОММИВОЯЖЁР. Полиномиальный алгоритм этой задачи неизвестен. Предположим, однако, что в некоторой индивидуальной задаче каким-то образом был получен ответ “да”, чтобы удостоверится в правильности ответа необходимо иметь маршрут, обладающий необходимыми свойствами. Имея этот маршрут, легко проверить, является ли он маршрутом, определить его длину, сравнить её с границей B, проверить высказанное утверждение. Эту процедуру проверки можно ограничить полиномом Length(I). Именно понятие полиномиальной проверяемости позволяет выделить задачи класса NP. Отметим, что проверяемость за полиномиальное время не влечёт разрешимости за полиномиальное время. Неформально класс NP можно определить понятием «недетерминированный алгоритм». Такой алгоритм состоит из двух стадий: стадии угадывания и стадии проверки.

По заданной индивидуальной задаче I на первой стадии происходит угадывание некоторой структуры S. Затем пара (I, S) подаётся в качестве входа на стадию проверки. Работа на этой стадии осуществляется обыкновенным детерминированным образом, в результате работы либо получается ответ “да”, либо ответ “нет”, либо вычисление продолжается бесконечно. Таким образом, недетерминированный алгоритм решает задачу распознавания П, если для любой индивидуальной задачи выполняются следующие два условия:

1.Если , то существует такая структураS, угадывание которой для входа I приведёт к тому, что стадия проверки, начиная работу на входе (I, S), заканчивает работу ответом “да”.

2.Если , то не существует такой структурыS, угадывание которой для входа I обеспечивало бы окончание стадии проверки на входе (I, S) ответом “да”.

Например, недетерминированный алгоритм задачи КОММИВОЯЖЁР, можно сформулировать следующим образом: на стадии угадывания формируемая структура S представляет собой некоторый маршрут, содержащий все города из списка; на стадии проверки подсчитывается длина маршрута и сравнивается с границей B.

Говорят, что недетерминированный алгоритм решает задачу распознавания П, работая в течение полиномиального времени, если найдётся такой полином p, что для любой найдётся некоторая догадкаS, приводящая на стадии детерминированной проверки на входе (I,S) к ответу “да” за время p(Length(I)).

Замечание: из определения следует, что размер угадываемой структуры S будет обязательно ограничен полиномом от Length(I) по длине кода.

Класс NP – это класс всех задач распознавания П, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за время, ограниченное полиномом p. Фактически, класс NP содержит задачи, правильность ответов которых можно проверить за полиномиальное время.

Имеется важное отличие классов P и NP.

Для класса P имеется симметрия между ответами “да” и “нет”, т.е. если задача I имеет вид: “Дано I, верно ли что для I выполнимо свойство x”. Если эта задача решаема за полиномиальное время, то за полиномиальное же время будут решаться и дополнительные задачи имеющий вид: “Дано I, верно ли что для I условие x не выполняется”.

Для задач класса NP исходная задача, принадлежащая классу NP, может породить дополнительную задачу, классу NP не принадлежащую.

Взаимоотношение между классами P и NP

Вопрос об этом взаимоотношении играет фундаментальную роль в теории NP полных задач. Одно соотношение известно точно . Действительно, если задача разрешима полиномиальным детерминированным алгоритмом, то недетерминированный алгоритм может быть получен следующим образом: в качестве указанной структурыS возьмём пустую структуру, а на стадии проверки используем полиномиальный детерминированный алгоритм решения задачи.

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

Теорема 1.

Если , то существует такой полином p, что П может быть решена детерминированным алгоритмом с временной сложностью O(2^p(n)).

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

Пусть A полиномиальный недетерминированный алгоритм решения задачи П. q(n) – полином, ограничивающий время работы алгоритма A. Не теряя общности можно сказать, что q может быть вычислен за полиномиальное время. Этого можно добиться, взяв, например, при достаточно большихc₁ и c₂. По определению класса NP для каждого входа длины n найдётся некоторое слово-догадка длины не более чем q(n). При этом алгоритм A на стадии проверки даст ответ “да” не более чем за q(n) шагов. Таким образом, общее число догадок, которое необходимо рассмотреть, не превосходит k^q(n), где k – количество символов в собственном алфавите V машины Тьюринга. Теперь можно детерминированным образом выяснить, имеет ли алгоритм A на заданном входе длины n принимающее вычисление. Для этого достаточно на каждой из k^q(n) догадок запустить детерминированную стадию проверки алгоритма A. При этом мы позволим алгоритму работать либо до момента, когда он остановится, либо когда он сделает q(n) шагов. Описанный моделирующий алгоритм выдаёт ответ “да”, если ему встретится слово-догадка, приводящее к принимающему вычислению с временем работы не более чем q(n), иначе ответом будет “нет”. Этот алгоритм является детерминированным решением задачи П и его временная сложность будет равна q(n)k^q(n). При подходящем выборе полинома p(n), это величина не превосходит O(2^p(n)) ч.т.д.

Большое количество задач, типа КОММИВОЯЖЁР или ИЗОМОРФИЗМ ПОДГРАФУ, принадлежат NP, и, несмотря на длительные рассмотрения этих задач большим количеством исследователей, полиномиального алгоритма до сих пор не найдено, поэтому широко распространено мнение, что NPP. Хотя доказательство этого факта до сих пор отсутствует, со значительной долей уверенности можно предполагать, что класс NP имеет структуру:

NP

Полиномиальная сводимость и NP-полные задачи

Будем говорить, что имеет место полиномиальная сводимость языка к языку, если существует функцияудовлетворяет двум условиям:

1. Существует ДМТ-программа, вычисляющая функцию с временной сложностью, ограниченной полиномом.

2. Для любого ,.

Полиномиальная сводимость обозначается значком «». L₁L₂.

Лемма 1.

Если L₁L₂, то ( также эквивалентно высказывание).

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

Пусть и– алфавиты языковL₁ и L₂, а функция осуществляет полиномиальную сводимость. Пусть M – ДМТ-программа вычисленияf, M₂ – полиномиальная ДМТ-программа распознания L₂. Полиномиальная ДМТ-программа распознавания L₁ может быть получена композицией программ M и M₂. Ко входу применяем программу M для того, чтобы построить. Затем кf(x) применяется программа M₂, которая выясняет справедливость отношения . Так как по определению сводимости, то описанная ДМТ-программа распознает языкL₁. Полиномиальность этой программы следует из полиномиальности программ M и M₂. Точнее, если p и p₂ – полиномы, ограничивающие время работы программ M и M₂, то , и, следовательно, время работы только что определённой программы ограничено функцией, которая является полиномом от длиныx ч.т.д.

Если П₁ и П₂ – задачи распознавания, e₁ и e₂ – их схемы кодирования, то будем писать (относительно заданных схем кодирования), если существует полиномиальная сводимость языкак. На уровне задач полиномиальная сводимость задачи распознаванияП₁ к задаче распознания П₂ означает наличие функции , удовлетворяющей двум условиям:

1) f вычисляется полиномиальным алгоритмом.

2) Для всех ,.

ПРИМЕР.

Пусть G=(V, E) – граф с множеством вершин V и рёбер E. Простым циклом в графе G называется такая последовательность <v₁, v₂, … , v_k> различных вершин из V, что ,-1, и .

Гамильтоновым циклом в графе G называется простой цикл, содержащий все вершины G.

Задача распознавания ГАМИЛЬТОНОВ ЦИКЛ (ГЦ) формулируется так:

Задан граф G=(V, E).

Вопрос: Верно ли, что граф G содержит гамильтонов цикл?

Покажем, что ГЦ сводится к задаче КОММИВОЯЖЁР. Для этого требуется указать функцию f, переводящую каждую индивидуальную задачу I из задачи ГЦ в некоторую индивидуальную задачу из задачи КОММИВОЯЖЁР; f должна удовлетворять двум условиям, записанным ранее.

Пусть G=(V, E), |V|=m определяет фиксированную индивидуальную задачу из массовой задачи ГЦ. Соответствующая индивидуальная задача из массовой задачи КОММИВОЯЖЁР определяется следующим образом. Множество городов C совпадает с множеством вершин графа V. Для любых двух городов расстояниеd(v_i, v_j)=1, если существует ребро в исходном графе (). Если ребро отсутствует, то соответствующее расстояние равно 2. В качестве границыB берётся величина m.

На неформальном уровне легко показать, что построенная функция преобразования f осуществляет сводимость и может быть вычислена за полиномиальное время. Для вычисления расстояний необходимо лишь выяснить принадлежность каждой пары вершин множествуE, т.е. не более указанного количества раз просмотреть это множество. Само вычисление значения m требует только однократного просмотра множества V, т.е. полиномиальные преобразования здесь очевидны. Для проверки справедливости второго требования необходимо показать, что граф G содержит гамильтонов цикл тогда и только тогда, когда в f(G) имеется проходящий через все города маршрут длины, не превосходящий B. Покажем это:

Пусть <v₁, v₂, …, v_m> – гамильтонов цикл в графе G, тогда <v₁, v₂, …, v_m> – маршрут длины m в задаче коммивояжёр f(G). Это так, поскольку для любой пары (v_i, v_i+1) и пары (v_m, v₁) имеются рёбра в исходном графе G, т.е. расстояния между городами равны 1.

Обратно:

Пусть <v_i1, v_i2, …, v_im> – маршрут в f(G), длина которого не превосходит B. Поскольку данный маршрут содержит ровно m пар городов, между которыми перемещается коммивояжёр, а любое расстояние в этой задаче не менее чем 1, то длина данного маршрута точно равна m. Следовательно, расстояние между каждой парой городов равно 1, это означает, что между каждой парой соответствующих вершин графа имеется ребро. Поэтому набор <v_i1,v_i2, …,v_im> определяет гамильтонов цикл в исходном графе G.

Итак, нами доказано, что ГЦ  КОММИВОЯЖЁР. В приведённом доказательстве имеются все элементы доказательства полиномиальной сводимости одной задачи к другой. Этот пример может служить моделью доказательства в общем случае.

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

Лемма 2.

Если и, то.

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

Пусть – алфавиты языковL₁, L₂, L₃, функция реализует, а функцияреализует. Тогда функция, которая для всехопределяется соотношениемf(x) = f₂(f₁(x)), реализует полиномиальную сводимость . Действительно,f(x)L₃  x L₁, а полиномиальность вычисления функции f доказывается рассуждениями, аналогичными в приведённой лемме 1.

Языки L₁ и L₂ (соответственно задачи распознавания П₁ и П₂) полиномиально эквивалентны, если они сводятся друг к другу, т.е. и. Лемма 2 означает, что отношение полиномиальной сводимости является отношением эквивалентности. Кроме того, отношение сводимости определяет частичное упорядочивание возникающих классов эквивалентности языков (задач распознавания). На самом деле классP – «наименьший» относительно этого частичного порядка класс эквивалентности и с вычислительной точки зрения его можно рассматривать как класс «самых лёгких» языков (задач распознавания). Класс NP-полных языков (задач распознания) даёт нам другой класс эквивалентности. В этом классе содержатся самые трудные языки (задачи распознавания) из класса NP.

Язык L называется NP-полным, если LNP и любой другой язык L’NP сводится к L. Исходя из свойств полиномиальной сводимости, можно сказать, что

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

труднорешаема, то и все NP-полные задачи труднорешаемы. Предположим, что PNP, тогда можно дать следующую уточнённую характеристику класса NP.

Показано, что помимо P и NPC класса должны существовать задачи из NP, неразрешимые за полиномиальное время и не являющиеся NP-полными. Нас в основном будут интересовать задачи из класса NP-полных задач. Для доказательства NP-полноты любой задачи, нужно показать, что к ней полиномиально сводятся все задачи класса NP.

Лемма 3.

Если L₁, L₂NP, L₁NPC и , тоL₂NPC.

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

Поскольку L₁NPC, то  L’ NP L’  L₁, тогда согласно лемме 2 имеем, что любая задача из NP сводится к L₂, т.е. L₂NPC.

На уровне задач распознавания эта лемма указывает простой путь доказательства NP-полноты, если нам известна хотя бы одна NP-полная задача.

Для доказательства NP-полноты задачи П необходимо показать:

1) П  NP.

2) Какая либо известная NP-полная задача полиномиально сводится к задаче П.

Наличие класса NP-полных задач доказывает теорема Кука.

Теорема Кука

Первой NP-полной задачей была задача распознавания из булевой логики, которая называется ВЫПОЛНИМОСТЬ. Термины для её описания следующие.

Пусть U={u₁, u₂, …, u_m} – множество булевых переменных. Под набором значений истинности на множестве U будем понимать функцию . Еслиt(u) = T, то будем говорить, что u принимает значение “истина”, если t(u)=F, то “ложь”. Если u – некоторая переменная из множества U, то u и будем называть литералами изU. Литерал u принимает значение “истина ” относительно t в том и только в том случае, когда переменная u принимает значение “истина”; литерал - принимает значение “истина ” относительноt в том и только в том случае, когда переменная u принимает значение “ложь”.

Дизъюнкцией над U назовём произвольное множество литералов над U, например . Она представляет дизъюнкцию этих литералов и называется выполненной при некотором наборе значений истинности тогда и только тогда, когда при рассматриваемом наборе значений истинности хотя бы один из её членов принимает значение “истина”. В нашем примере дизъюнкция будет выполнена относительноt, если одновременно не окажется, что t(u₁)=F, t(u₃)=T, t(u₈)=F.

Набор C дизъюнкций над U называется выполнимым в том и только в том случае, если найдётся некоторый набор значений истинности на множестве U, такой, что одновременно выполнены все дизъюнкции. Такой набор значений истинности называется выполняющим набором значений истинности для C.

Задача ВЫПОЛНИМОСТЬ формулируется следующим образом:

Заданы множество U и набор C дизъюнкции над U.

Вопрос: Существует ли выполняющий набор значений истинности для C?

Например, пусть U={u₁, u₂}, C=. Эта индивидуальная задача из ВЫП имеет ответ “да”. Выполняющее задание значений истинности определяется так:t(u₁)=t(u₂)=T. Для индивидуальной задачи, в которой C=, ответ будет “нет”.

Теорема Кука формулируется следующим образом:

Задача выполнимость является NP-полной.

Доказательство результатов об NP-полноте

Опираясь на Лемму 3, доказательство NP-полноты любой задачи П состоит из следующих четырёх шагов:

1. Доказательство того, что ПNP.

2. Отыскание некоторой задачи П’NPC из имеющегося обширного списка NP-полных задач.

3. Построение функции f, сводящей П’ к П.

4. Доказательство того, что функция f осуществляет полиномиальное сведение.

Шесть основных NP-полных задач

1.3-ВЫПОЛНИМОСТЬ (3-ВЫП)

Условие: Дан набор дизъюнкций C={c₁, c₂, …, c_m} на конечном множестве переменных U, причём |c_i|=3 при .

Вопрос: Существует ли на U набор значений истинности, при котором выполняются все дизъюнкции из C?

2.ТРЁХМЕРНОЕ СОЧЕТАНИЕ (3-С)

Условие: Дано множество MXYZ, причём множества X, Y и Z являются непересекающимися и имеют одинаковое число элементов q.

Вопрос: Верно ли, что M содержит 3-сочетание, т.е. некоторое подмножество M’M, такое, что |M’|=q и никакие два разных элемента M’ не имеют ни одной равной координаты?

3.ВЕРШИННОЕ ПОКРЫТИЕ (ВП)

Условие: Дан граф G=(V,E) и положительное целое число k, k|V|.

Вопрос: Имеется ли в графе G вершинное покрытие не более чем из k элементов, т.е. такое подмножество V’V, что |V’|  k и для каждого ребра {u, v}E хотя бы одна из вершин u или v принадлежит V’ ?

4.КЛИКА

Условие: Заданы граф G=(V,E) и положительное целое число J|V|.

Вопрос: Имеется ли в графе G клика мощностью не менее чем J, т.е. такое подмножество V’V, что |V’|J и любые две вершины из V’ соединены ребром из E?

5.ГАМИЛЬТОНОВ ЦИКЛ (ГЦ)

Условие: Дан граф G=(V, E).

Вопрос: Верно ли, что граф G=(V,E) содержит гамильтонов цикл.

6.РАЗБИЕНИЕ

Условие: Заданы конечное множество A и «вес» s(a) N каждого aA.

Вопрос: Существует ли подмножество A’ множества А такое, что.

Можно привести следующую схему, которая указывает последовательность сведения задач при доказательстве их NP-полноты. На рисунке стрелка указывает, какая NP-полная задача сводится к исследуемой задаче.

Некоторые методы доказательства NP-полноты

Имеется несколько общих приёмов из большого количества подходов доказательства NP-полноты, которые широко используются. Эти приёмы:

а) Сужение задачи.

б) Локальная замена.

в) Построение компонент.

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

Сужение задачи

Данный метод является самым простым и широко используемым. Если мы доказываем, что некоторая задача ПNP является NP-полной, то здесь пытаемся установить, что имеется некоторая известная NP-полная задача П’, которая является просто частным случаем П. Сущность метода заключается в том, чтобы указать дополнительное ограничение, которое требуется наложить на индивидуальные задачи из П, чтобы получилась в результате этого сужения задача из П’. При этом не требуется, чтобы возникающая новая задача была точной копией известной NP-полной задачи. Таким образом, метод сужения можно рассматривать просто как иной взгляд на задачу, а не стандартный способ доказательства.

ПРИМЕРЫ доказательства методом сужения:

Рассмотрим задачу ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ (ТП-3).

Условие: Задано конечное множество X такое, что |X|=3q, и семейство C трехэлементных подмножеств множества X.

Вопрос: Верно ли, что семейство C содержит точное покрытие множества X, т.е. такое подсемейство C’C, что каждый элемент из X содержится ровно в одном элементе из C’.

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

Заметим, что любую индивидуальную задачу 3-С можно рассматривать как индивидуальную задачу из ТП-3, просто считая, что M состоит из неупорядоченных троек разных элементов множества XYZ. При этом 3-сочетания для индивидуальной задачи из 3-С взаимнооднозначно соответствуют точным покрытиям соответствующей индивидуальной задачи из ТП-3. То есть задача 3-С есть ограниченная версия задачи ТП-3, что доказывает NP-полноту задачи ТП-3.

Задача РЮКЗАК.

Условие: Задано конечное множество U, веса элементов s(u)N, стоимости элементов v(u)N, общие ограничение BN на размеры, стоимость kN.

Вопрос: Существует ли подмножество такое, что .

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

Если ограничиться рассмотрением только таких задач, в которых для всех uU s(u)=v(u) и , то мы придём к задаче РАЗБИЕНИЕ, которая является NP-полной, что доказывает NP-полноту.

Заметим, что описанный метод хорошо работает тогда, когда имеется обширный список известных NP-полных задач. Многие возникающие на практике задачи часто представляют собой усложнённые задачи из списка имеющихся NP-полных задач.

Локальная замена

Этот метод состоит в том, что выбирается некоторое характерное свойство известной NP-полной задачи, с помощью него образуется семейство основных модулей, а соответствующие индивидуальные задачи исследуемой задачи получаются путём единообразной замены каждого основного модуля некоторой другой структурой. Важным моментом является то, что каждая замена приводит только к локальному изменению структуры, причём замены не зависят друг от друга.

Задача РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Условие: Задан граф G=(V,E), число вершин которого кратно 3, т.е. |V|=3q.

Вопрос: Существует ли такое разбиение V на q непересекающихся подмножеств V₁,V₂, …, V_q, каждое из которых содержит ровно 3 элемента, и для каждого V_i={v_i1, v_i2, v_i3} рёбра {v_i1, v_i2}, {v_i2, v_i3}, {v_i3, v_i1} принадлежат E.

Сведём задачу ТП-3 к задаче РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Пусть множество X (|X|=3q) и семейство C его трёхэлементных подмножеств образуют условие произвольной индивидуальной задачи из ТП-3. Построим граф =(,) такой, что ||=3q’ и для него существует искомое разбиение тогда и только тогда, когда семейство C содержит точное покрытие множества.

Основными модулями рассматриваемой индивидуальной задачи из ТП-3 будут трёхэлементные подмножества из C. Операция локальной замены превращает каждое элементарное подмножество C_i=(x_i, y_i, z_i)C в набор E_i, состоящий из 18 рёбер. Этопреобразование можно изобразить следующим образом.

Таким образом, формируемый граф будет таким:

Заметим, что по построению только вершины из множества X могут быть инцидентны более чем одному множеству E_i. Кроме того, количество вершин ||=3q+9|С|=3q’, где С – семейство трёхэлементных подмножеств.

Индивидуальную задачу РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ можно построить за полиномиальное время из задачи ТП-3. Если c₁, c₂, …, c_q – трёхэлементные подмножества из C, которые образуют ТП-3, то соответствующее разбиение V на треугольники V₁, V₂, …, V_q’ строится следующим образом. Если c_i=(x_i, y_i, z_i) – элемент точного покрытия, то из множества E_i выбираются элементы: (x_i, a_i[1], a_i[2]) (y_i, a_i[4], a_i[5]) (z_i, a_i[7], a_i[8]) (a_i[3], a_i[6], a_i[9]). Если же элемент C_i=(x_i, y_i, z_i) не входит в точное покрытие, то из множества E_i выбираются тройки (a_i[1], a_i[2], a_i[3]) (a_i[4], a_i[5], a_i[6]) (a_i[7], a_i[8], a_i[9]). Такой выбор элементов обеспечивает то, что каждый элемент из множества X содержится ровно в одном трёхвершинном подмножестве рассматриваемого разбиения.

Обратно, если V=V₁V₂V₃ … V_q’ – произвольное разбиение графа G на треугольники, то соответствующее точное покрытие множества X получается, если выбирать те подмножества c_i, для которых (a_i[3], a_i[6], a_i[9])=V_j при некотором j, 1 ≤ j ≤ q’.

Приведённый пример представляет собой доказательство метода локальной замены в “чистом виде”. Здесь структура рассматриваемой индивидуальной задачи однозначно определялась структурой исходной задачи (NP-полнота которой известна).

Часто оказывается полезным дополнить рассматриваемую индивидуальную задачу вспомогательными элементами, которые играют роль ограничителя, налагающего дополнительные ограничения на способы получения ответа “да”.

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

Задача УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ.

Условие: Задано конечное множество заданий T. Для каждого tT заданы целые числа r(t)0 – время готовности, когда должно быть завершено задание, директивный срок d(t)N₀, длительность l(t)N₀.

Вопрос: Существует ли для T допустимое расписание, т.е. такая функция : TN₊₀ со следующими свойствами:

1) (t)  r(t).

2) (t)+l(t)  d(t).

3)  t’T t’t  (t’)+l(t’)(t) или (t)+l(t)(t’).

Другими словами, задание t выполняется с момента времени (t) до момента (t)+l(t), оно не может быть начато ранее момента r(t), должно быть закончено не позднее d(t), и временной интервал выполнения задания t не может перекрываться с временным интервалом другого задания t’.

Докажем, что данная задача NP-полная. Используя метод локальной замены, сведём её к NP-полной задаче РАЗБИЕНИЕ.

Пусть индивидуальная задача РАЗБИЕНИЕ задаётся конечным множеством A и размером всех элементов s(a) (aA); пусть значение . В качестве базисных модулей данной индивидуальной задачи выступают отдельные элементыaA. Пусть at_a, r(t_a)=0, d(t_a)=B+1, l(t_a)= s(a). В качестве ограничителя возьмём ещё одно задание t, такое, что r(t)=B/2, d(t)=(B+1)/2, l(t)=1.

Подобное преобразование, очевидно, требует полиномиального времени. Ограничения, которые накладывает дополнительное задание t, носят двоякий характер. Во-первых, этот ограничитель не позволяет строить

расписание, если B нечётно (в этом случае и исходная задача разбиение и сводимая задача не имеют решения), т.к. в этом случае r(t)=d(t) и t не может быть включено в расписание. Поэтому в дальнейшем мы будем рассматривать только ситуацию, когда B чётно. Тогда мы имеем для ограничителя t следующее значение r(t)=B/2, d(t)=r(t)+1. Из этого свойства следует, что (t)=B/2. Отсюда время, доступное для обработки всех остальных заданий, делится на 2 блока, как это указано на рисунке.

Таким образом, задача составления расписания превращается в задачу выбора подмножества заданий, которые будут выполняться раньше задания t и подмножества заданий, которые будут выполняться после t. Такой выбор возможен только в том случае, если мы найдём множество A’ такое, что , таким образом, для рассматриваемой индивидуальной задачи РАЗБИЕНИЕ искомое множествоA’ существует тогда и только тогда, когда для соответствующей индивидуальной задачи УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ существует допустимое расписание, что и доказывает NP-полноту.

Метод построения компонент

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

ПРИМЕР

Докажем NP-полноту задачи УПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ.

Условие: Задано множество T заданий, каждое из которых имеет длительность 1, для каждого задания t задан директивный срок d(t)N₀; частичное упорядочивание (<·) на множестве T и целое неотрицательное k|T|.

Вопрос: Существует ли расписание  : T{0,1,2, … , |T|-1}, такое, что:

1) tt’(t)(t’).

2) (t)<(t’), если t <· t’.

3) |{tT: (t)+1d(t)}|  k.

Докажем NP-полноту задачи.

Пусть граф G=(V, E) и положительное целое число J (J|V|) образуют индивидуальную задачу из массовой задачи КЛИКА. Соответствующая индивидуальная задача из задачи УПОРЯДОЧЕНИЕ С МИНИМАЛЬНЫМ ЗАПАЗДЫВАНИЕМ имеет множество заданий T=VE, величина k=|E|-J(J-1)/2. Частичное упорядочивание заданий определяется следующим образом:

t <· t’  tV, t’E и вершина t инцидентна ребру t’;

Таким образом, компонента, соответствующая каждой вершине, состоит из единственного задания с директивным сроком |V|+|E|, а компонента, соответствующая каждому ребру, состоит из единственного задания с директивным сроком J(J+1)/2. Благодаря наличию частичного порядка на множестве T в искомом расписании задание, соответствующее ребру, будет следовать за заданиями, соответствующими его вершинам. Поэтому задания, для которых имеется опасность запаздывания, обязательно соответствуют рёбрам. Искомое расписание удобно представить себе схематически следующим рисунком: vvbvbvvbvbvbvbvbvbvbvbvbvbvbvvbvv

Первые две части из четырёх частей расписания можно рассматривать как компоненту выбора клики. До этого срока может быть выполнено не более J(J+1)/2 заданий. Для того, чтобы число запоздавших заданий не превосходило заданной вершины k, в начале должны стоять, по крайней мере, J(J-1)/2 заданий, соответствующих рёбрам. Однако если задание, соответствующее ребру, выполняется ранее своего директивного срока, то и задания, соответствующие его концевым вершинам, должны быть закончены раньше этого срока. Минимально возможное количество вершин, которые могут быть инцидентны J(J-1)/2 различным рёбрам, равно J (причём такая ситуация возможна только тогда, когда эти рёбра образуют полный граф на указанных J вершинах). Отсюда следует, что среди заданий, выполняющихся ранее директивного срока, должно иметься, по крайней мере, J заданий, соответствующих вершинам. Однако до директивного срока заданий, соответствующих рёбрам, может быть выполнено не более J(J+1)/2 - J(J-1)/2 = J заданий, отвечающих вершинам. Следовательно, в любом таком расписании до директивного срока заданий, соответствующих рёбрам, должно закончится ровно J заданий, соответствующих вершинам, и ровно J(J-1)/2 – рёбрам, что соответствует клике исходного графа G. Обратно, если клика существует, то расписание можно построить способом, указанном на рисунке.

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

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

В ситуации, которая описана, нельзя полагаться на интуицию, поскольку очень часто NP-полные задачи при незначительном изменении условий превращаются в полиномиально разрешимые. Например, задачи 3-ВЫП и 3-С NP-полны, а близкие им задачи 2-ВЫП и ПАРОСОЧЕТАНИЕ разрешимы за полиномиальное время. Таким образом, при анализе задач лучше пользоваться двухсторонним подходом: с одной стороны пытаться найти полиномиальный алгоритм, а с другой пытаться доказать NP-полноту задачи. Мы рассмотрим ситуацию, когда NP-полнота задачи доказана. Далее будет рассмотрен указанный двухсторонний подход для более глубокого анализа этой задачи.

Анализ подзадач

Несмотря на то, что некоторая задача является NP-полной, необходим её дальнейший анализ. Это связано с тем, что обычно доказанная задача является некоторой идеализацией решаемой конкретной прикладной задачи. При этом могут быть упущены некоторые конкретные детали исходной задачи. Если мы их примем в учёт, то вполне возможно, что задача станет полиномиально разрешимой. Кроме этого, возможно, что индивидуальные задачи, плохо поддающиеся решению, не очень многочисленны. Вполне возможно, что они обладают некоторыми характерными свойствами, которые позволяют их заблаговременно опознать. Описанные возможности могут быть изучены при помощи анализа подзадач исходной задачи. П’ является подзадачей задачи П, если в ней сформулирован тот же вопрос, что и в П, но только на некотором подмножестве множества индивидуальных задач из П.

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

Очевидно, что если задача П является NP-полной, то её подзадачи могут быть как NP-полными, так и полиномиально разрешимыми. В предположении, что PNP, можно считать, что подзадачи любой NP-полной задачи лежат по разные стороны воображаемой границы, которая разделяет полиномиальные и труднорешаемые задачи. На самом деле, при анализе подзадач лучше в каждый момент представлять себе «пограничную зону» между двумя типами задач. С одной стороны от неё лежат NP-полные задачи, с другой стороны – полиномиально разрешимые, в самой же «пограничной зоне» лежат задачи, NP-полнота которых остаётся под вопросом.

ПРИМЕР.

Задача РАСПИСАНИЕ С ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ.

Условие: Задано множество T заданий с длительностью выполнения 1. Задан частичный порядок на множестве заданий. Указано число процессоров m и общий директивный срок DN.

Вопрос: Существует ли такое расписание  :T{0,1,2,…,D}, что для каждого i{0,1,2,…,D} |{tT: (t)=i}|  m и если t <· t’,то (t)<(t’).

В качестве гипотетического приложения задачи рассмотрим следующую ситуацию. Предположим, что вы получили задание помочь поступившим первокурсникам составлять план своих занятий на всё время обучения. В данной ситуации студенты представляют вам список всех курсов, которые они намереваются прослушать – это и есть множество заданий T, число m – это максимальное количество курсов, которое они могут слушать одновременно. Величина D – это количество семестров обучения. Предполагается, что университет достаточно большой, так что каждый курс лекций читается каждый семестр, и никакие два курса не пересекаются по времени. Однако некоторые курсы являются вспомогательными для других и поэтому должны быть прослушаны раньше, эта особенность создаёт частичный порядок. Предположим, что мы хотим написать программу на компьютере для решения задачи. Задача расписания с отношением предшествования является NP-полной. Тем не менее, возможно найдутся некоторые естественные ограничения, приемлемые для большинства студентов и облегчающие решение задачи. Поскольку работоспособность студентов ограничена, то вполне вероятно, что величину m можно сверху ограничить каким-либо числом. Вспомогательные курсы лекций также могут удовлетворять дополнительным ограничениям. Например, некоторые студенты могут выбрать очень разнообразную программу обучения, при этом ни один из выбранных ими курсов не потребует вспомогательных курсов, в этом случае условие порядка отсутствует. В некоторых случаях может оказаться, что для каждого курса лекций требуется только один явный вспомогательный курс, а все остальные курсы, вспомогательные для первого, являются вспомогательными и для явного вспомогательного. В данном случае, частичный порядок представляет собой древовидную структуру. Возможны и другие ограничения. Если рассматривать только эти два ограничения (на количество слушаемых курсов и тип частичного порядка), то можно представить состояние знаний о семействе подзадач задачи РАСПИСАНИЕ С ОТНОШЕНИЕМ ПРЕДШЕСТВОВАНИЯ в виде следующего рисунка:

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

Техника, используемая для доказательства NP-полноты подзадач, аналогична описанной ранее для изолированных задач. Но здесь имеется одно существенное отличие: когда мы пытаемся доказать NP-полноту подзадачи, нам уже известно доказательство NP-полноты некоторой обобщённой версии этой подзадачи. Это сразу нам подсказывает кандидата на известную NP-полную задачу. Кроме того, мы уже имеем доказательство NP-полноты, которое можно попытаться модифицировать для получения доказательства NP-полноты соответствующей подзадачи. Рассмотрим этот подход на примере.

РАСКРАШИВАЕМОСТЬ ГРАФА В ТРИ ЦВЕТА.

Условие: Задан граф G=(V, E).

Вопрос: Верно ли, что граф G раскрашиваем в три цвета, т.е. существует ли такая функция f:V{1, 2, 3}, что f(u)f(v), если {u, v}E?

Сама по себе эта задача представляет собой частный случай задачи РАСКРАШИВАЕМОСТЬ ГРАФА В K ЦВЕТОВ. k – число, входящее в условие задачи, f : V{1, 2, 3, …, k}. (задача РАСКРАШИВАЕМОСТЬ ГРАФА В К ЦВЕТОВ является NP-полной).

Мы будем рассматривать задачу, вводя некоторые ограничения. Первое из них состоит из ограничения максимальной степени вершин. Большинство задач из теории графов может быть решено за полиномиальное время, если максимальная степень вершин достаточно мала. Например, если потребовать, чтобы все вершины графа имели степень не более двух, то задача ГЦ, ВЕРШИННОЕ ПОКРЫТИЕ и РАСКРАШИВАЕМОСТЬ ГРАФА В ТРИ ЦВЕТА тривиально решаемы за полиномиальное время. Таким образом, возникает вопрос, каково самое сильное ограничение на степени вершин, при котором задача остаётся NP-полной. Задача КЛИКА – одна из задач, для которых никакое ограничение на степени вершин не сохраняет свойства NP-полноты.

Это свойство объясняется тем, что если степени вершин ограничены величиной D, то граф не может содержать клику, состоящую более чем из D единиц вершин. Значит, наибольшая клика может быть получена, если мы переберём все подмножества вершин, состоящих не более чем из D+1 элементов. Количество таких подмножеств ограничено полиномом.

Замечание:

Хотя количество ограничено полиномом для любого D, однако, при больших N и D время решения уже не будет приемлемым. Для многих других задач имеются NP-полные подзадачи с ограниченной степенью вершин. Некоторые представлены в следующей таблице:

	 P, при D 	NPC, при D 
ВП	2	3
ГЦ	2	3
РАСКРАШИВАЕМОСТЬ ГРАФА В 3 ЦВЕТА	3	4
МНОЖЕСТВО ВЕРШИН РАЗРЕЗАЮЩИХ КОНТУР	2	3

Каждый из представленных результатов об NP-полноте подзадач может быть получен из общей задачи методом локальной замены. Основная идея при доказательстве заключается в замене вершин. Другое общее ограничение для задачи из теории графов состоит в требовании планарности графов.

Граф называется планарным, если его можно отобразить на листе бумаги так, что ни какие два ребра не пересекаются (единственно возможные точки пересечения – общие вершины). Например, при составлении географической карты и при конструировании печатных схем возникают планарные графы. Задача КЛИКА снова даёт нам пример задачи, которая при наложении указанного условия упрощается. Это связано с тем, что никакой планарный граф не может содержать полного подграфа более чем на четырёх вершинах.

Рассмотрим в качестве примера задачу МАКСИМАЛЬНЫЙ РАЗРЕЗ.

Условие: Заданы граф G=(V, E), веса w(e)N каждого eE, и натуральное число k.

Вопрос: Можно ли разбить множество V на два непересекающихся подмножества V₁ и V₂ таких, что сумма весов рёбер, имеющих в качестве концевых точек вершины из разных подмножеств, была не меньше чем k.

Для произвольных графов эта задача NP-полна даже в том случае, если потребовать, чтобы веса всех рёбер были равны. Однако показано, что теория паросочетаний может быть использована для нахождения полиномиального алгоритма решения этой задачи для планарных графов, при этом веса рёбер могут быть произвольные. С другой стороны, большинство из уже рассмотренных задач на графах остаются NP-полными и для планарных случаев. Для доказательства NP-полноты в ситуации планарных графах обычно используется два подхода:

1) Состоит в том, чтобы найти NP-полную задачу для планарного графа и свести её к исследуемой на NP-полноту задаче, сводимость при этом должна сохранять планарность.

2) Применение локальной замены к исходному графу. Для этого конструируется “переплетение”, которое является планарным графом и которое может быть использовано вместо любого пересечения рёбер при плоскостном изображении графа.

Задачи с числовыми параметрами и сильная NP-полнота

Необходимость анализа подзадач NP-полной задачи особенно ярко проявляется в задачах с числовыми параметрами. Причину этого можно продемонстрировать на примере применения метода «динамического программирования» для решения задачи разбиение.

В задаче разбиение заданы множество A={a₁, a₂, … a_n} и веса элементов s(a₁), s(a₂), …, s(a_n). Положим . ЕслиB нечётно, то, очевидно, ответ в задаче будет “нет”. Если же B чётно, то можно применить следующий подход. Рассмотрим функцию t(i, j), где 1 i n, 0jB/2. Значение этой функции определяет истинность утверждения «существует такое подмножество множества {a₁, a₂, … a_i}, что сумма размеров его элементов равна j». Значение этой функции можно представить в виде таблицы.

Таблица заполняется построчно сверху вниз. Первая строка заполняется очевидным образом: значение истинности только в те ячейки, где j=0 или j=s(a₁), все остальные ячейки заполнены значением “ложь”. Все следующие строки заполняются с использованием значений предыдущей строки, при этом t(i, j)=T, либо при t(i-1, j)=T, либо при s(a_i)  j и t(i-1, j- s(a_i))=T. Исходная задача разбиение даёт ответ “да” в том случае, когда значение таблицы t(n,B/2)=T. Рассмотрим заполнение таблицы на следующем примере:

A={a₁,…, a₅} s(a₁)=1, s(a₂)=9, s(a₃)=5, s(a₄)=3, s(a₅)=8; B=26

i/j

0

1

2

3

4

5

6

7

8

9

10

11

12

13

1

T

T

2

T

T

T

T

3

T

T

T

T

T

T

4

T

T

T

T

T

T

T

T

T

T

T

5

T

T

T

T

T

T

T

T

T

T

T

T

Как видно из решения, алгоритм является полиномиальным алгоритмом со сложностью порядка количества элементов таблицы, т.е. nB. Может показаться, что этот алгоритм даёт полиномиальное решение задачи разбиение. Однако это не так, поскольку мы предполагаем, что используется разумная схема кодирования. Для таких схем кодирования любое целое число s(a_i) представляется на входе цепочкой длины не более чем log₂s(a_i). Это означает, что длина входа будет порядка nlog₂B. Величина nB не может быть ограничена полиномом от величины nlog₂B, т.е. задача не является полиномиально разрешимой.

Наличие подобного алгоритма показывает, что NP-полнота задачи разбиение в значительной степени зависит от того обстоятельства, что на входе могут присутствовать чрезвычайно большие числа. Если на величину входных чисел было бы положено ограничение, например, в виде полинома от размера задачи, то приведённый алгоритм для этой ограниченной задачи был бы полиномиальным. Алгоритмы с таким свойством называются «алгоритмами с псевдополиномиальным временем работы». На практике большое количество задач имеют входные данные, удовлетворяющие предложенному ограничению. Однако и в ситуациях, когда такое ограничение не выполняется, псевдополиномиальные алгоритмы полезны. Они будут работать экспоненциально долго только для тех индивидуальных задач, которые имеют экспоненциально большие числа. Однако может оказаться, что в интересующих нас приложениях подобные индивидуальные задачи встречаются редко, т.е. псевдополиномиальный алгоритм будет служить почти всегда так же хорошо, как и полиномиальный. Однако не все задачи с числовыми параметрами имеют алгоритмы, подобные рассмотренному. С помощью теории NP-полноты можно показать, что для некоторых задач не может существовать даже псевдополиномиального алгоритма. Введём некоторые дополнительные определения. В этих определениях учитывают подзадачи, которые получаются при наложении ограничений на величины чисел, входящих в индивидуальную задачу. Эти ограничения формулируются с помощью двух не зависящих от кодирования функций.

Length : D_ПN,

Max : D_ПN.

Функция Length сопоставляет любой индивидуальной задаче число, соответствующее длине описания этой задачи. Функция Max сопоставляет индивидуальной задаче число, соответствующее величине максимального числа. Результаты, которые в дальнейшем будут получены, справедливы для достаточно широкого класса полиномиально эквивалентных функций Length и Max. Будем говорить, что функции Length и Length’ полиномиально эквивалентны, если существуют полиномы p и p’ такие, что для любой индивидуальной задачи ID_П: Length(I)  p’(Length’(I)),

Length’(I)  p (Length (I)).

Будем говорить, что пара функций Max и Length полиномиально эквивалентно Max’ и Lenght’, если:

1) Функции Length и Length’ полиномиально эквивалентны.

2) Существуют такие полиномы от двух переменных q и q’, что для всех ID_П

Max(I)  q’ (Max’(I), Length’ (I)),

Max’(I)  q (Max (I), Length (I)).

В качестве примера рассмотрим функции Max и Length, которые задаются для задачи раЗбиение. В этой задаче любая индивидуальная задача задаётся конечным множеством A и размерами всех элементов s(a_i).

Функцию Max можно выбрать следующим образом:

; ;

В качестве функции Length можно выбрать любую из следующих функций:

Любая из девяти пар, заданных функциями Max и Length, полиномиально эквивалентна любой другой паре. Понятие полиномиальной эквивалентности пар функций Max и Length позволяет при построении доказательств не указывать конкретно эти функции, а ссылаться только на разумность кодировки. Предлагаемые функции имеют целочисленные значения, а числовые параметры могут представлять собой более сложные образования. Такие числа будем рассматривать как совокупность нескольких целых чисел. Примем следующее соглашение: в качестве значения Max(I) будем выбирать либо величину наибольшего числа, входящего в I, либо 0, если в I не входят числа. От функции Length и Max потребуем выполнения ещё одного условия. При любой фиксированной разумной схеме кодирования должны существовать две ДМТ-программы с полиномиальным временем работы. Они, принимая на входе условие произвольной индивидуальной задачи, выдают двоичные записи величин Max(I), Length(I). Это требование необходимо, поскольку мы будем рассматривать ограничения на индивидуальные задачи, которые формируются с помощью этих функций.

Следующие определения предполагают, что с массовой задачей П связаны функции Max и Length, обладающие ранее указанными свойствами. Алгоритм решения задачи П будет называться псевдополиномиальным (по времени) алгоритмом, если его временная функция ограничена сверху полиномом от (Length(I), Max (I)). По определению, любой полиномиальный алгоритм является также и псевдополиномиальным, поскольку ограничен сверху полиномом от первого аргумента (Length(I)). NP-полнота задачи не обязательно исключает возможность её решения псевдополиномиальным алгоритмом. Многие из рассмотренных нами задач обладают тем свойством, что величина Max(I) ограничена полиномом от Length(I), поэтому для таких задач нет различия между полиномиальным и псевдополиномиальным алгоритмами. Например, в задаче клика единственный числовой параметр J ограничен количеством вершин графа. Задача выполнимость не содержит чисел, за исключением индексов, литералов, дизъюнкций, этими числами можно пренебречь, поскольку они играют роль имён. Принятое нами соглашение о разумной схеме кодирования гарантирует, что имена будут ограничены полиномом Length(I).

Выделим класс задач, которые будут рассматриваться в данном разделе. Будем называть задачу П задачей с числовыми параметрами, если не существует такого полинома p, что для любой задачи ID_П Max(I)p(Length(I)). Среди шести основных NP-полных задач единственной задачей с числовыми параметрами является задача разбиение.

Замечание 1.

Если NP-полная задача П не является задачей с числовыми параметрами, то П не может быть решена псевдополиномиальным алгоритмом (если справедливо, что P  NP).

Для произвольной задачи П и полинома p с целыми коэффициентами обозначим через П_p подзадачу, получаемую из П рассмотрением только тех индивидуальных задач I, для которых выполняется Max(I)p(Length(I)). Задача П_p уже не является задачей с числовыми параметрами. Если задача П разрешима псевдополиномиальным алгоритмом, то задача П_p разрешима полиномиальным алгоритмом. Задачу П назовём NP-полной в сильном смысле, если ПNP и существует такой полином p с целыми коэффициентами, что задача П_p является NP-полной.

В частности, если NP-полная задача не является задачей с числовыми параметрами, то она NP-полна в сильном смысле.

Замечание 2.

Если задача П NP-полна в сильном смысле, то она не может быть решена псевдополиномиальным алгоритмом (PNP).

Благодаря этому замечанию мы получаем средства для применения теории NP-полноты к вопросам существования псевдополиномиальных алгоритмов.

Доказательство результатов о сильной NP-полноте

Наиболее прямой путь доказательства сильной NP-полноты состоит в том, чтобы для некоторого полинома p доказать NP-полноту задачи П_p. Например, задача коммивояжёр представляет собой задачу с числовыми параметрами, её NP-полнота доказывается сведением к ней задачи ГЦ. При этом сведении получаются только такие индивидуальные задачи, для которых расстояние между вершинами графов равно 1 или 2, а граница B равняется числу городов m. Таким образом, если взять в качестве Max(I) максимум из значения границы B и наибольшего расстояния между городами и положить

,

то все индивидуальные задачи, получаемые в этой сводимости, будут удовлетворять соотношению Max(I)  Length(I), это означает, что мы имеем соответствующее свойство задачи. Задача коммивояжёр получается при сводимости, обладает свойством, указанным в неравенстве, и при этом является NP-полной. Следовательно, задача КОММИВОЯЖЕР NP-полна в сильном смысле, значит, псевдополиномиальный алгоритм для неё не существует.

Для того, чтобы доказать, что некоторая задача NP-полна в сильном смысле, полезно иметь задачу с числовыми параметрами, NP-полную в сильном смысле, и с её помощью доказывать результаты о сильной NP-полноте других задач. Такой задачей будет седьмая основная NP-полная задача 3-разбиение.

Условие: Заданы множество A из 3m элементов, граница BN, размеры всех элементов aA s(a)N, причём B/4<S(a)<B/2 и .

Вопрос: Можно ли A разбить на m непересекающихся подмножеств S₁, S₂, …, S_m, таких, что . Ограничения на размеры элементов приводят к тому, что каждое из множествS_i содержит ровно по три элемента.

Доказательство сильной NP-полноты для данной задачи проходит в два этапа.

Сначала доказывается, что близкая к ней задача 4-разбиение NP-полна в сильном смысле. 4-разбиение формулируется аналогично, только |A|=4m, B/5<S(a)<B/3, т.е. каждое из множеств разбиения будет содержать по четыре элемента.

Докажем NP-полноту в сильном смысле задачи 3-разбиение.

Доказательство принадлежности к классу NP - самостоятельно.

Сначала сведём задачу 3-С к задаче 4-разбиение. Для этого в задаче 4-разбиение будем рассматривать только те индивидуальные задачи, для которых . В этом случае у нас сохраняется ограниченность размеров элементов полиномом от общего числа элементов.

Пусть A={a₁, a₂, …, a_4n}, граница B, размеры элементов s(a_i), - задают произвольную индивидуальную задачу из 4-разбиение. Для размеров выполняется условие B/5<S(a)<B/3, s(a_i)2¹⁶|A|⁴. Соответствующая индивидуальная задача из 3-разбиение будет содержать 24n²-3n элементов: по одному для каждого элемента из A, по два элемента для каждой пары элементов из A и 8n²-3n «заполняющих» элементов. Каждому отдельному элементу из множества A сопоставим регулярный элемент w_i, имеющий размер s’(w_i)=4(5B+s(a_i))+1. Каждой паре элементов (a_i, a_j)A соответствует два «спаривающих» элемента u[i, j] и . Их веса

Наконец, для 1k8n²-3n имеется «заполняющий» элемент размераs’()=20B. Граница B’ конструируемой индивидуальной задачи 3-разбиение будет B’=64B+4.

Остаётся показать, что такое преобразование является полиномиальным, а также, что все размеры элементов лежат в пределах B’/4<s(a)<B’/2. Сумма размеров всех элементов равна B’(2n²-n). Поскольку размеры элементов исходного множества A ограничены величиной 2¹⁶|A|⁴, то и размеры индивидуальной задачи из 3-разбиение будут ограничены полиномом от мощности A, это означает ограничение полиномом от числа элементов построенной задачи, т.е. и от её длины. Чтобы завершить доказательство NP-полноты в сильном смысле, осталось показать, что в построенной индивидуальной задаче для 3-разбиение ответ “да” будет тогда и только тогда, когда существует 4-разбиение в сводимой задаче.

Предположим, что сводимая индивидуальная задача имеет 4-разбиение. Каждое из подмножеств имеет по четыре элемента, допустим, это будут элементы {a_i, a_j, a_k, a_l}. Соответствующее ей 3-разбиение строится следующим образом: 4-множество {a_i, a_j, a_k, a_l} разбивается произвольным образом на два элемента {a_i, a_j} {a_k, a_l}. Искомое 3-разбиение будет содержать 3-множества: {w_i, w_j, u[i, j]}

{w_k, w_l, }. Можно было использовать другие спаривающие элементы: вместоu[i, j], вместо[i, j]. Сумма размеров элементов этих множеств равна B’, это следует из того, что s(a_i)+s(a_j)+s(a_k)+s(a_l)=B. Выполняя указанную процедуру для каждого из n 4-множеств, мы получим 2n 3-множеств, последние будут содержать все «регулярные» элементы, а также n связных пар, состоящих из «спаривающих» элементов. После этого останутся незаписанными в 3-множество 8n²-3n пар «спаривающих» элементов и столько же «заполняющих» элементов. Поскольку при построении сумма размеров каждой пары «спаривающих» элементов равна 44B+4=B’-20B, то каждая такая связанная пара может быть сгруппирована с одним из оставшихся заполняющих элементов, в результате мы получаем 3-разбиение.

Обратно:

Пусть построенная задача имеет 3-разбиение, требуется доказать, что исходная задача имеет 4-разбиение.

Если мы будем рассматривать остатки при делении на 4 размеров элементов, то мы увидим, что ни одно из 3-множеств не может содержать по 3 спаривающих элемента. Ни одно из 3-множеств не может содержать два регулярных и один заполняющий элемент. Таким образом, заданное 3-разбиение содержит 2n 3-множеств, каждое из которых содержит 2 регулярных и один спаривающий элемент, кроме того, имеется 8n²-3n 3-множеств, которые содержат 2 спаривающих и 1 заполняющий элемент. Рассмотрим любое из 3-множеств последнего типа.

Пусть u[i, j] – один из спаривающих элементов 3-множества. Если другой спаривающий элемент – u[s, t], то его размер равен размеру элемента (по построению весов элементов и величинеB’). Поэтому элементы u[s, t] и могут быть поменяны местами (в соответствующих 3-множествах). Описанную операцию по замене можно повторять до тех пор, пока не получится 3-разбиение, в котором каждый заполняющий элемент окажется в одном 3-множестве со связанной паройu[i, j], . В результате этого оставшиеся спаривающие элементы входят в подмножества совместно с регулярными элементами. Некоторые из 3-множеств также разбиваются на пары, всего получаетсяn пар 3-множеств регулярных элементов.

Поскольку два спаривающих элемента в каждой такой паре оказываются связанными, сумма их размеров равна 44B+4. Поэтому сумма размеров 4 регулярных элементов, входящих в эти два 3-множества, должна быть равна 84B+4. Отсюда следует, что соответствующие 4 элемента исходного множества A из задачи 4-разбиение образуют 4-множество. Следовательно, n пар 3-множеств, которые мы рассмотрели, порождают искомое 4-разбиение, ч.т.д.

Заметим, что если эту сводимость рассматривать как сводимость общей задачи 4-разбиение к задаче 3-разбиение, то она не доказывала бы сильную NP-полноту задачи 3-разбиение. Для получения результата о сильной NP-полноте существенно рассмотрение NP-полной подзадачи задачи 4-разбиение, в которой величина ограничена полиномом от размерности задачи, однако конкретный вид полинома в этой оценке несущественен. Для нас было бы удобно, если бы была возможность оперировать со сводимостью подобного типа без необходимости вдаваться в детали подзадач и полиномов. Этого можно достичь с помощью следующих определений и леммы.

Определение 1.

Пусть П и П’ – произвольные задачи распознавания; D_П и D_П’ – множества их индивидуальных задач; Y_П и Y_П’ – множество индивидуальных задач с ответом “да”; Max, Lenght, Max’, Lenght’ – соответствующие функции максимума и длины записи.

Говорят, что задача П псевдополиномиально сводится к задаче П’, если существует функция f : D_П  D_П’ , обладающая следующими свойствами:

1.  ID_П, IY_П  f(I)Y_П’

2. Функция f может быть вычислена за время, ограниченное полиномом от двух переменных Max(I), Length(I).

3. Существует полином q₁ такой, что для всех ID_П справедливо неравенство: q₁(Length’(f(I)))  Length(I).

4. Существует такой полином q₂ от других переменных, что для всех индивидуальных задач ID_П выполнено неравенство: Max’(f(I))  q₂(Max(I), Length(I)).

Лемма.

Если задача П NP-полна в сильном смысле, а задача П’NP и П – псевдополиномиально сводится к задаче П’, то П’ – NP-полная в сильном смысле задача.

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

Пусть f – функция, реализующая псевдополиномиальную сводимость; q₁, q₂ - соответствующие полиномы, описанные в определении. Без потери общности можно предположить, что полиномы q₁ и q₂ имеют целые положительные коэффициенты. Поскольку задача П – NP-полна в сильном смысле, то существует такой полином p, что задача П_p является NP-полной. Полином p можно выбрать так, что у него будут только целые неотрицательные коэффициенты.

Определим полином следующим образом:Справедливо следующее: функцияf, будучи ограниченной для индивидуальной задачи из множества , осуществляет полиномиальные сведения задачи к задаче , что доказываетNP-полноту задачи . Сначала проверим, что любая индивидуальная задачаIП_p при отображении f переходит в индивидуальную задачу из. По определению задачии неравенств, которыми удовлетворяют многочленыq₁ и q₂ получаем:

Max’(f(I))  q₂(Max(I), Length(I)) q₂(p(Length(I)),

Length(I))  q₂(p(q₁(Length’(f(I)))), q₁(Length’(f(I))))=(Length’(f(I))).

Таким образом, индивидуальная задача f(I) . Из первого и второго условия псевдополиномиальной сводимости и того, что для любой индивидуальной задачи IП_p, Max(I)  p(Length(I)) следует, что f удовлетворяет требованиям к полиномиальной сводимости. Следовательно, задача NP-полная, а задача П’ NP-полная в сильном смысле, лемма доказана.

Доказанная лемма освобождает от необходимости иметь дело с конкретными подзадачами П_p при доказательстве результатов о сильной NP-полноте, но при этом возникает необходимость проверять дополнительные условия на функцию f, осуществляющую псевдополиномиальную сводимость.

Рассмотрим их повнимательнее. Условие 1 совпадает с одним из условий определений обычной полиномиальной сводимости. Условие 2 почти совпадает со вторым условием, однако оставляет несколько больше свободы при выборе сложности функции. Условие будет выполнено почти для всех сводимостей, поскольку оно требует лишь того, чтобы сводимость не приводила к значительному уменьшению длины входа.

Наиболее важным условием определения является определение 4. Оно требует, чтобы величина наибольшего числа в конструируемой индивидуальной задаче не росла экспоненциально, в зависимости от функции Max и Length в индивидуальной исходной задаче. Например, ту конструкцию, которую мы использовали при доказательстве сильной NP-полноты 3-разбиение, можно рассматривать как псевдополиномиальное сведение.

Задача упорядочивание внутри интервалов NP-полна в сильном смысле.

Условие: Задано конечное множество задач T, для каждой tT, r(t)0 – время готовности к обработке, кроме того, дан директивный срок d(t)N и длительность l(t)N.

Вопрос: Существует ли для T допустимое расписание, т.е. такая функция  : TN₊₀, что для всех tT

1. (t)  r(t);

2) (t)+l(t)  d(t);

3)  t’ T\{t}; или (t’)+l(t’)  (t), или (t’)  (t)+l(t).

Построим псевдополиномиальное сведение задачи 3-разбиение к задаче упорядочивание внутри интервала:

A={a₁, a₂, … a_3m}, BN. Веса S(a₁), S(a₂), … S(a_3m) определяют задачи из 3-разбиение. Соответствие индивидуальной задачи из упорядочивание внутри интервалов строится следующим образом:

T=A{t_i:1i<m}.

, где l(t) – время обработки задания;

, где r(t) – время готовности;

, где d(t) – директивный срок работы.

Описанная сводимость может быть выполнена за полиномиальное время только по отношению к длине записей входной информации. Длина исходных задач, получаемых при таком сведении, полиномиально эквивалентна длине исходных задач, т.е. условия 2 и 3 определения выполняются. При сведении наибольшее число построенной индивидуальной задачи равно mB+m-1, следовательно, выполняется условие 4, остаётся показать, что выполнено условие 1.

В любой последовательности заданий, удовлетворяющей условиям построенной задачи, задание t_i должно выполняться в промежутке времени от iB+i-1 до iB+i, что можно изобразить следующим рисунком:

Таким образом, мы имеем m интервалов, каждый — длины B. Поскольку совокупная длина интервалов равна последнему сроку выполнения самого последнего задания, то все пустые блоки должны быть полностью заполнены выполняющимися заданиями. Таким образом, эти блоки играют в задаче упорядочивание внутри интервалов ту же роль, что и множество S₁, S₂, …, S_n в задаче 3-разбиение, значит условие 1 также выполняется, и мы имеем псевдополиномиальную сводимость задачи, поэтому задача упорядочивание внутри интервалов NP-полна в сильном смысле ч.т.д.

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

Временная сложность как функция натуральных параметров

До сих пор мы рассматривали подзадачи из-за того, что на практике истиной целью является решение конкретной задачи, а не самой общей массовой задачи. Зная очертания пограничной области между NP-полными и полиномиально разрешимыми подзадачами, мы сможем решать конкретную подзадачу, двигаясь в наиболее перспективном направлении. С другой стороны, результаты, полученные относительно подзадач, могут быть использованы в качестве ориентира при поиске алгоритма решения общей задачи. Если общая задача оказывается NP-полной, то при справедливости PNP для её решения могут существовать только экспоненциальные алгоритмы. Однако различные алгоритмы решения могут оказаться в различной степени “экспоненциальными”. При этом одни из них могут оказаться для нас предпочтительнее других. Это связано с тем, что в практических задачах мы имеем дело с конкретными параметрами, а не с искусственно созданной длиной входа. В задаче расписание для мультипроцессорной системы набор естественных параметров включает следующие величины:

• число заданий n;

• число процессоров m;

• длительность L самого продолжительного задания.

Результат о NP-полноте этой задачи утверждает, что она не может быть решена за время, ограниченное полиномом от трёх переменных n, m, log L. Однако можно задаться вопросом: существует ли алгоритм, временная сложность которого ограничена полиномом от mⁿ и logL, или от n^m и logL, или от n, m, L, или от (nL)^m. Полученные результаты о сложности подзадач проливают некоторый свет на эти вопросы. Исходный результат о NP-полноте рассматриваемой задачи показывает в действительности, что подзадача, в которой m ограничено числом 2, является NP-полной, поэтому для решения задачи не может существовать алгоритма, временная сложность которого ограничена полиномом от n^m и logL, для такой подзадачи этот алгоритм был бы полиномиален. В то же время, полученные результаты не исключают возможности существования алгоритма, временная сложность которого ограничивалась бы полиномом mⁿ logL (в действительности алгоритмы полного перебора с такой временной сложностью могут быть построены). Поскольку задача, которую мы рассматриваем, является, кроме того, NP-полной в сильном смысле, это исключает существование алгоритмов, полиномиальных по n, m, L. Однако этот результат оставляет открытым вопрос о существовании алгоритма, полиномиального по (nL)^m (такой алгоритм давал бы псевдополиномиальный алгоритм при каждом фиксированном m).

Задача расписание для мультипроцессорной системы.

Условие: Задано множество A заданий; длительности l(a)N для всех aA, число m процессов, mN, директивное число DN.

Вопрос: Существует ли разбиение A на m непересекающих подмножеств A=A₁A₂…A_m, такое, что .

NP-полнота доказывается методом сужения сведением задачи 3-разбиение, а NP-полнота в сильном смысле доказывается сведением к ней задачи 4-разбиение.

Таким образом, рассматривая подзадачи, возникающие из исходной задачи при ограничении одного или нескольких из её естественных параметров, мы получаем полезную информацию о возможных типах алгоритмов решения общей задачи. Однако чтобы обеспечить выразимость функции Length(I) в виде полинома от параметров, выбранных нами в качестве достаточных представителей размера индивидуальной задачи, нужно принять особые меры предосторожности (необходимо, чтобы для исходной задачи класс построенных полиномиальных алгоритмов совпадал с классом алгоритмов, полиномиальных относительно невыбранных параметров, в остальном можно выбирать любые параметры, которые представляются естественными и адекватно отражающими смысл задачи). Из общего результата об NP-полноте будет вытекать, что задачу нельзя решить за время, ограниченное полиномом от всех выбранных параметров, но информация, получаемая при ограничении этих параметров, может иметь большое значение в связи с существованием общих алгоритмов других типов. Методы, аналогичные методам отыскания сильной NP-полноты, можно применять и к задачам, не имеющим числовые параметры (в нашем определении). Дело в том, что в любой задаче неявно присутствуют числовые параметры, такие как мощности множеств, значение границ и т.д. Например, NP-полнота задачи 3-выполнимость не допускает алгоритма для задачи выполнимость, временная сложность которого ограничена полиномом от (mn)^M:

m – число дизъюнкций,

n – число литералов,

M – максимальное число литералов в одной дизъюнкции.

С другой стороны, для задачи клика существует алгоритм с временной оценкой n^D, где n – число вершин графа, D – максимальная степень вершин. Таким образом, теория NP-полных задач может служить ориентиром не только при поиске полиномиальных алгоритмов, но и экспоненциальных.