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

А теперь рассмотрим некоторые вычислительно сложные задачи, основанные на арифметических операциях с числами. Как вы увидите, вычислительная неразрешимость в данном случае обусловлена способом кодирования некоторых из представленных ранее задач в представлении очень больших целых чисел.

Задача о суммировании подмножеств

Базовой задачей в этой категории будет задача о суммировании подмножеств — частный случай задачи о рюкзаке, рассмотренной в разделе 6.4 при рассмотрении динамического программирования. Версия этой задачи с принятием решения может быть сформулирована следующим образом:

Задано множество натуральных чисел w₁, ..., w_n и целевое число W. Существует ли подмножество {w₁, ..., w_n} сумма которого равна ровно W?

Мы уже видели алгоритм для решения этой задачи; почему же сейчас она включается в список вычислительно сложных задач? Все возвращается к проблеме, которая была впервые упомянута при знакомстве с задачей о суммировании подмножеств в разделе 6.4. Разработанный тогда алгоритм выполнялся за время O(nW), которое может быть разумным при малых W, но становится безнадежно неприемлемым при больших W (и числах w.). Для примера возьмем экземпляр со 100 числами, длина каждого из которых составляет 100 бит. В этом случае входные данные состоят всего из 100 х 100 = 10 000 цифр, но значение W равно приблизительно 2¹⁰⁰.

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

Эта проблема встречается во многих ситуациях; например, мы встречали ее в контексте алгоритмов сетевого потока, в которых пропускные способности были целочисленными. Возможно, другие примеры тоже покажутся вам знакомыми — например, безопасность такой криптографической системы, как RSA, обусловлена сложностью факторизации числа из 1000 битов. Но если бы время выполнения из 2¹⁰⁰⁰ шагов считалось приемлемым, факторизация такого числа не создавала бы никаких трудностей.

Здесь стоит ненадолго задержаться и спросить себя: действительно ли это представление полиномиального времени для числовых операций является таким уж жестким ограничением? Например, для двух натуральных чисел w₁ и w₂, представленных в записи по основанию d (для некоторого d > 1), сколько времени займут операции сложения, вычитания или умножения? Эта тема была затронута в разделе 5.5, когда мы заметили, что стандартный способ выполнения этих операций, изучаемый на школьных уроках математики, имеет полиномиальное время выполнения (с малым показателем степени). Сложение и вычитание (с переносом) выполняется за время O(log w₁ + log w₂), тогда как стандартный алгоритм умножения выполняется за время O(log w₁ ∙ log w₂). (Вспомните, что в разделе 5.5 обсуждался асимптотически быстрый алгоритм умножения, который дети вряд ли самостоятельно откроют на уроках математики.)

Итак, основной вопрос: возможно ли решение задачи о суммировании подмножеств алгоритмом с (действительно) полиномиальным временем? Другими словами, существует ли алгоритм с временем выполнения, полиномиальным по n и log W? Или полиномиальным только по n?

Доказательство NР-полноты задачи о суммировании подмножеств

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

(8.23) Задача о суммировании подмножеств является NP-полной.

Доказательство. Сначала покажем, что задача о суммировании подмножеств принадлежит NP. Для заданных натуральных чисел w₁, ..., w_n и целевого значения W сертификатом, подтверждающим существование решения, будет подмножество w_i1, ..., w_in, которое в сумме дает W. За полиномиальное время мы можем вычислить сумму этих чисел и убедиться в том, что она равна W.

Теперь попробуем свести заведомо NР-полную задачу к задаче о суммировании подмножеств. Так как мы ищем множество, которое в сумме дает заданную величину (а не ограничивается ею сверху или снизу), речь идет о комбинаторной задаче, основанной на получении точного значения. Задача о трехмерном сочетании является естественным кандидатом; мы покажем, что Трехмерное сочетание ≤_Р Сумма подмножеств. Основная хитрость будет связана со способом кодирования операций с множествами посредством суммирования целых чисел.

Рассмотрим экземпляр задачи о трехмерном сочетании, определяемый множествами X, Y, Z, каждое из которых имеет размер n, и множеством m триплетов T ⊆ X х Y х Z. Стандартный способ представления множеств основан на использовании битовых векторов: каждый элемент векторов соответствует разным элементам множества, и равен 1 в том, и только в том случае, если множество содержит этот элемент. Мы воспользуемся этим методом для представления триплетов t = (x_i, y_j, z_k) ∈ T: мы строим число w_t c 3n цифрами, которое содержит 1 в позициях i, n + j и 2n + k и 0 во всех остальных позициях. Другими словами, для некоторого основания d > 1 w_t = d^i-1 + d^n+j-1 + d^2n+k-1.

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

В текущей ситуации эта проблема решается простым приемом. Всего используется m чисел, каждое состоит из цифр 0 или 1; если предположить, что наши числа записаны по основанию d = m+ 1, то переносов не будет вообще.

Построим следующий экземпляр задачи о суммировании подмножеств. Для каждого триплета t = (x_i, y_j, z_k) ∈ T строится число w_t в записи по основанию m + 1, как определяется выше. Затем Wопределяется как число в записи по основанию m + 1 с 3n цифрами, каждая из которых равна 1, то есть

Утверждается, что множество Т триплетов содержит идеальное трехмерное сочетание в том, и только в том случае, если существует подмножество чисел {w_t}, которое дает в сумме W. Предположим, существует идеальное трехмерное сочетание триплетов t₁, ..., t_n. В этом случае в сумме w_t1 + ... + w_tn, в каждой из 3n позиций находится одна единица, поэтому результат равен W. И наоборот, предположим, существует множество чисел w_t1, ..., w_tk, которое в сумме дает W. Тогда, поскольку в представлении каждого w_t1 содержатся три единицы и переносы отсутствуют, мы знаем, что k = n. Следовательно, для каждой из 3n позиций цифр ровно одно из w_t1 содержит 1 в этой позиции. Следовательно, t₁, ..., t_k образуют идеальное трехмерное сочетание. ■

Расширения: сложность некоторых задач планирования

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

Допустим, дано множество из n задач, которые должны выполняться на одном компьютере. Для каждого задания i установлено время доступностиr_i, когда оно впервые становится доступным для обработки; предельное времяd_i, к которому оно должно быть завершено; и продолжительность обработкиt_i. Будем считать, что все эти параметры являются целыми числами. Чтобы задание i было завершено, ему должен быть выделен смежный набор из t_i единиц времени где-то в интервале [r_i, d_i]. В любой момент на машине может выполняться только одно задание. Вопрос заключается в следующем: можно ли спланировать все задания для выполнения так, чтобы каждое задание было завершено к предельному времени? Назовем этот экземпляр задачей планирования с временем доступности и предельным временем.

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

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

Теперь покажем, что задача о суммировании подмножеств сводится к этой задаче планирования. Рассмотрим экземпляр задачи о суммировании подмножеств с числами w₁, ..., w_n и целевым значением W. При построении эквивалентного экземпляра задачи планирования сначала бросается в глаза обилие параметров, которыми необходимо управлять: время доступности, предельное время и продолжительность. Здесь важно пожертвовать большей частью этой гибкости и получить “облегченный” экземпляр задачи, который, тем не менее, кодирует задачу о суммировании подмножеств.

Пусть Мы определяем задания 1, 2, ..., n; задание i имеет время доступности 0, предельное время S + 1 и продолжительность w_i. Задания из этого множества можно расположить в любом порядке, и все они завершатся вовремя.

Теперь мы установим дополнительные ограничения для экземпляра, чтобы решить его можно было только группировкой подмножества заданий, продолжительности которых в сумме дают ровно W. Для этого мы определяем (n + 1)-е задание с временем доступности W, предельным временем W + 1 и продолжительностью 1.

Рассмотрим любое действительное решение этого экземпляра задачи планирования. (N + 1)-е задание должно выполняться в интервале [W, W + 1]. Между общим временем доступности и общим предельным временем свободны S единиц времени; и суммарная продолжительность заданий также равна S. Таким образом, на машине не должно быть простоев, когда не выполняется ни одно задание. В частности, если до времени W выполняются задания i₁, ..., i_k, то соответствующие числа w_i1, ..., w_ik в экземпляре задачи о суммировании подмножеств в сумме дают ровно W.

И наоборот, если существуют числа w_i1, ..., w_ik, которые в сумме дают ровно W, их можно распланировать до задания n + 1, а остальные — после задания n + 1; и это расписание будет действительным решением для экземпляра задачи планирования. ■

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

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

Рассмотрим особый случай задачи о суммировании подмножеств с n входными числами, в котором W ограничивается полиномиальной функцией n. В предположении, что P ≠ NP, этот частный случай не является NP-полным.

Он не является NP-полным по той простой причине, что не может быть решен за время O(nW) нашим алгоритмом динамического программирования из раздела 6.4; когда W ограничивается полиномиальной функцией n, это алгоритм с полиномиальным временем.

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

Для заданного графа G, не являющегося связным, и числа k существует ли подмножество связных компонентов, размер объединения которых равен в точности k?

Неправильное утверждение. Задача о группировке компонентов является NP-полной.

Неправильное доказательство. Задача о группировке компонентов принадлежит NP, доказательство не приводится. Теперь мы попытаемся показать, что Суммирование подмножеств ≤_PГруппировка компонентов. Для заданного экземпляра задачи о суммировании подмножеств с числами w₁, ..., w_n и целевого значения W экземпляр задачи группировки компонентов строится следующим образом: для каждого i строится путь P_i длины w_i. Граф G представляет собой объединение путей P₁, ..., P_n, каждый из которых является отдельным связным компонентом. Мы присваиваем k = W. Очевидно, что G содержит множество связных компонентов, объединение которых имеет размер к в том, и только в том случае, если некоторое подмножество чисел w₁, ..., w_n в сумме дает W. ■

Ошибка в этом “доказательстве” весьма коварна; в частности, утверждение в последнем предложении истинно. Проблема в том, что построение, описанное выше, не устанавливает, что Суммирование подмножеств ≤_P Группировка компонентов, потому что эта задача требует более чем полиномиального времени. При построении входных данных для “черного ящика”, решающего задачу группировки компонентов, нам пришлось построить систему кодирования графа с размером w₁ + ... + w_n, а это требует времени, экспоненциального по размеру входных данных экземпляра задачи о суммировании подмножеств. По сути, задача о суммировании подмножеств работает с числами w₁, ..., w_n в чрезвычайно компактном представлении, но задача группировки компонентов не получает “компактную” кодировку графа.

Проблема более фундаментальна, чем неправильность этого доказательства; на самом деле задача группировки компонентов может быть решена за полиномиальное время. Если n₁, n₂, ..., n_G— размеры связных компонентов G, мы просто используем наш алгоритм динамического программирования для задачи о суммировании подмножеств, чтобы принять решение о том, дает ли некоторое подмножество этих чисел {n_i} в сумме k. Необходимое для этого время выполнения равно O(сk); и поскольку и с, и k ограничиваются n, получается время O(n²).

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