Сумма подмножества и псевдополином: трудность, которая сидит в числах

Если ты объяснишь, почему таблица на n · S клеток не делает задачу полиномиальной, отличишь слабо NP-полную задачу от сильно NP-полной и сведёшь разбиение к сумме подмножества, - листай до «Теперь сам».

Как думаешь, кто ошибся

В разделе о динамическом программировании рюкзак решался таблицей: строки - предметы, столбцы - вместимость, время n · W. Произведение двух чисел - явно многочлен. А в каталоге NP-полных задач рюкзак стоит на видном месте.

Ответь себе до чтения: если NP-полная задача решается за n · W, значит ли это, что P = NP? Не значит. Многочлен должен быть от длины входа, а W в запись входа попадает своими цифрами. Вместимость в миллиард - это десять цифр и миллиард столбцов таблицы. Алгоритм быстрый по отношению к числу W и медленный по отношению к его записи.

На что это похоже

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

Таблица по сумме - такой справочник: по клетке на каждое значение. Её размер определяется не тем, сколько чисел дано, а тем, насколько они велики: каждая лишняя цифра в числе увеличивает таблицу вдесятеро.

Механизм: таблица, длина записи и два вида трудности

Сумма подмножества: даны n натуральных чисел и цель S; есть ли подмножество с суммой ровно S. Сертификат - само подмножество, так что задача в NP; она NP-полна - к ней сводится 3-SAT, само сведение здесь не приводится.

Таблица. Заведём массив dostizhimo[0 … S]: можно ли набрать сумму s из уже просмотренных чисел. Сначала достижим только ноль. Для каждого числа x идём по суммам от S вниз и помечаем s, если достижима s − x. Вниз - чтобы не взять одно число дважды: при обходе снизу вверх сработала бы пометка, только что поставленная этим же числом. Всего не больше n · S действий.

Длина входа. Число S записывается b ≈ log₂ S битами, то есть S ≈ 2ᵇ. Время таблицы:

n · S   =   n · 2ᵇ          многочлен от n,  экспонента от b

Добавь к каждому числу на входе два двоичных знака - вход вырастет на несколько бит, а таблица вчетверо.

Алгоритм, время которого - многочлен от длины входа и от величины наибольшего числа на входе, называется псевдополиномиальным. Он полиномиален, если числа записывать палочками - пятёрку как |||||, так что длина входа равна самой величине, - и экспоненциален при обычной записи.

Слабая и сильная NP-полнота.

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

сильно NP-полная   остаётся NP-полной, даже если все числа не больше
                   многочлена от n, например не больше n²
                   упаковка в контейнеры, коммивояжёр, разбиение
                   на группы по три числа с равными суммами,
                   и все задачи без чисел: SAT, клика, раскраска,
                   гамильтонов цикл

У сильно NP-полной задачи псевдополиномиального алгоритма нет, если P ≠ NP: при числах не больше n² время вида n · S само было бы многочленом от n, то есть алгоритм стал бы настоящим полиномиальным. Поэтому вопрос «велики ли числа» полезен только для первой группы.

Родственники. Разбиение: можно ли разделить числа на две части с равными суммами. Это сумма подмножества с целью «половина общей суммы». В обратную сторону сведение тоже есть: чтобы узнать, набирается ли сумма S из чисел с общей суммой T, сначала сравнивают: если S больше T, ответ «нет». Иначе добавляют два числа, 2T − S и T + S, и спрашивают о разбиении. Задачи сводятся друг к другу, значит, равны по трудности.

Правило

Сумма подмножества решается таблицей за n · S действий, но это время экспоненциально по длине записи S; такие алгоритмы называют псевдополиномиальными. NP-полные задачи, у которых они есть, называют слабо NP-полными: они трудны только при больших числах. Сильно NP-полные задачи остаются трудными при малых числах, и псевдополиномиального алгоритма для них нет, если P ≠ NP.

Разбор: числа становятся длиннее, таблица - шире

Восемь чисел и две цели: достижимая и недостижимая. Потом все числа и цели умножаются на 4 и на 16 - каждое умножение на 4 добавляет два бита к записи каждого числа. Функция tablicej считает действия таблицы, pereborom - число подмножеств.

def tablicej(chisla, cel):
    dostizhimo = [False] * (cel + 1)
    dostizhimo[0] = True
    shagov = 0
    for x in chisla:
        for s in range(cel, x - 1, -1):
            shagov = shagov + 1
            if dostizhimo[s - x]:
                dostizhimo[s] = True
    return [dostizhimo[cel], shagov]

def pereborom(chisla, cel):
    najdeno = False
    for maska in range(2 ** len(chisla)):
        summa = 0
        for i in range(len(chisla)):
            if maska >> i & 1 == 1:
                summa = summa + chisla[i]
        if summa == cel:
            najdeno = True
    return [najdeno, 2 ** len(chisla)]

chisla = [3, 5, 9, 14, 20, 27, 33, 41]
for mnozhitel in [1, 4, 16]:
    bolshie = []
    for x in chisla:
        bolshie.append(x * mnozhitel)
    print(mnozhitel, tablicej(bolshie, 77 * mnozhitel),
          tablicej(bolshie, 151 * mnozhitel))
print(pereborom(chisla, 77), pereborom(chisla, 151))

1 [True, 472] [False, 1064]
4 [True, 1864] [False, 4232]
16 [True, 7432] [False, 16904]
[True, 256] [False, 256]

Сумма 77 набирается, сумма 151 - нет: общая сумма чисел 152, и единицу из них не составить. Ответы от умножения не меняются - задача по существу та же.

А работа таблицы меняется: 472, 1864, 7432 действия (меньше n · S, потому что для числа x обход идёт только до x). Почти вчетверо на каждое умножение на четыре, то есть на каждые два бита в записи чисел. Вход - восемь чисел и цель 77 - вырос с 42 до 78 бит, меньше чем вдвое, а работа почти в шестнадцать раз. Перебор подмножеств на величину чисел не смотрит: 256 подмножеств в любом случае, по восемь действий на каждое.

Отсюда практическое правило выбора. Чисел тридцать, каждое до тысячи - таблица: в ней до тридцати тысяч клеток, а действий - до миллиона. Чисел тридцать, каждое до 10¹⁸ - таблица невозможна, перебор 2³⁰ медленный, и нужен третий способ - разделить числа на две половины, выписать все 2¹⁵ сумм каждой и для каждой суммы первой половины искать недостающее до S двоичным поиском в отсортированных суммах второй. Это около 2¹⁵ · 15 действий вместо 2³⁰.

Разбор: разбиение и сумма подмножества - одна задача

Функция est_razbienie решает разбиение через сумму подмножества. Функция summa_cherez_razbienie делает обратное: решает сумму подмножества, имея только решатель разбиения. Сравним второе с прямым перебором на восьми целях.

def est_summa(chisla, cel):
    for maska in range(2 ** len(chisla)):
        summa = 0
        for i in range(len(chisla)):
            if maska >> i & 1 == 1:
                summa = summa + chisla[i]
        if summa == cel:
            return True
    return False

def est_razbienie(chisla):
    vsego = sum(chisla)
    if vsego % 2 == 1:
        return False
    return est_summa(chisla, vsego // 2)

def summa_cherez_razbienie(chisla, cel):
    vsego = sum(chisla)
    if cel > vsego:
        return False
    return est_razbienie(chisla + [2 * vsego - cel, vsego + cel])

chisla = [3, 5, 9, 14, 20]
napryamuyu = []
cherez = []
for cel in [8, 10, 17, 23, 30, 37, 51, 52]:
    napryamuyu.append(est_summa(chisla, cel))
    cherez.append(summa_cherez_razbienie(chisla, cel))
print(napryamuyu)
print(cherez)
print(est_razbienie([3, 5, 9, 14, 20, 1]),
      est_razbienie([3, 5, 9, 14, 20, 3]))

[True, False, True, True, False, True, True, False]
[True, False, True, True, False, True, True, False]
True False

Две первые строки совпали на всех восьми целях. Почему сведение верно: общая сумма исходных чисел T, добавлены 2T − S и T + S, новая общая сумма - 4T, половина - 2T. Два добавленных числа в одну половину не помещаются: вместе они дают 3T. Значит, они в разных половинах, и той, где лежит 2T − S, не хватает ровно S - их нужно набрать из исходных чисел.

Последняя строка - само разбиение: числа с добавленной единицей делятся поровну (20 + 5 + 1 и 14 + 9 + 3, по 26), а с добавленной тройкой - нет, хотя сумма 54 чётная.

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

Что ломается без этого

«Есть таблица - значит, задача лёгкая». Таблица лёгкая, пока суммы малы. Цены в копейках, время в миллисекундах, объёмы в байтах превращают рюкзак на сто предметов в таблицу на миллиарды столбцов.

Числа дробные. Таблица индексируется целыми суммами. Перевод дробей в целые умножением на знаменатель делает суммы огромными.

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

По виду задачи судят о её силе. Разбиение на две части слабо NP-полно. Разбиение на тройки с равными суммами сильно NP-полно. Формулировки почти одинаковые.

Зачем это в работе

Первый вопрос к числовой задаче: каков диапазон значений? Бюджет до миллиона единиц при сотне позиций - это сто миллионов действий над таблицей в миллион клеток, считается за секунды. Тот же бюджет в копейках требует в сто раз больше и времени, и памяти.

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

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

Теперь сам

1. Сто предметов, вместимость рюкзака 10⁶. Сколько действий сделает таблица? А при вместимости 10¹²?
2. Все числа на входе умножили на 1000. Как изменилось время таблицы и время перебора подмножеств?
3. Как решить задачу о разбиении, имея программу для суммы подмножества?
4. Почему алгоритм со временем n · S не доказывает, что P = NP?
5. К какой группе относится задача коммивояжёра и что из этого следует для таблиц по длине маршрута?