Проблема суммы подмножества

Проблема суммы подмножества (SSP) — это проблема принятия решений в информатике . В самой общей формулировке существует мультимножество . $S$ целых чисел и целевой суммы $T$ , и вопрос состоит в том, чтобы решить, будет ли сумма любого подмножества целых чисел точно равна $T$ . ^[1] Известно, что задача NP-полная . Более того, некоторые его ограниченные варианты также являются NP-полными, например: ^[1]

Вариант, в котором все входы положительны.
Вариант, в котором входы могут быть положительными или отрицательными, и $T=0$ . Например, учитывая набор $\{-7,-3,-2,9000,5,8\}$ , ответ — да, потому что подмножество $\{-3,-2,5\}$ сумма равна нулю.
Вариант, в котором все входные данные положительны, а целевая сумма равна ровно половине суммы всех входных данных, т. е. $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ . Этот особый случай SSP известен как проблема разделов .

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

SSP — это частный случай задачи о рюкзаке и задачи о сумме множественных подмножеств .

Вычислительная сложность [ править ]

Сложность во время выполнения SSP зависит от двух параметров:

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

Поскольку и n, и L растут, SSP становится NP-трудным. Сложность наиболее известных алгоритмов экспоненциальна по меньшему из двух n и L. параметров Проблема является NP-сложной, даже если все входные целые числа положительны (и целевая сумма T является частью входных данных). Это можно доказать прямым сокращением от 3SAT . ^[2] Это также можно доказать путем редукции трехмерного сопоставления (3DM): ^[3]

Нам дан экземпляр 3DM, где наборами вершин являются W, X, Y. Каждый набор имеет n вершин. Имеется m ребер, каждое из которых содержит ровно по одной вершине из каждого из W, X, Y. Обозначим L := потолок(log ₂ ( m +1)), так что L больше количества битов, необходимых для представления количество ребер.
Мы создаем экземпляр SSP с m положительными целыми числами. Целые числа описываются их двоичным представлением. Каждое входное целое число может быть представлено 3 битами nL , разделенными на 3 n зон по L бит. Каждая зона соответствует вершине.
Для каждого ребра (w,x,y) в экземпляре 3DM существует целое число в экземпляре SSP, в котором ровно три бита равны «1»: младшие биты в зонах вершин w, x и й. Например, если n =10 и L=3 и W=(0,...,9), X=(10,...,19), Y=(20,...,29), то ребро (0, 10, 20) представлено числом (2 ⁰+2 ³⁰+2 ⁶⁰).
Целевая сумма T в экземпляре SSP устанавливается в целое число с «1» в младшем бите каждой зоны, то есть (2 ⁰+2 ¹+...+2 ^3н-1).
Если экземпляр 3DM имеет идеальное совпадение, то суммирование соответствующих целых чисел в экземпляре SSP дает ровно T.
И наоборот, если экземпляр SSP имеет подмножество с суммой ровно T, то, поскольку зоны достаточно велики, чтобы не было «переносов» из одной зоны в другую, сумма должна соответствовать идеальному совпадению в экземпляре 3DM.

Следующие варианты также известны как NP-сложные:

Входные целые числа могут быть как положительными, так и отрицательными, а целевая сумма T = 0. Это можно доказать путем приведения к варианту с положительными целыми числами. Обозначим этот вариант SubsetSumPositive, а текущий вариант — SubsetSumZero. Учитывая экземпляр ( S , T добавив один элемент со значением — T. ) SubsetSumPositive, создайте экземпляр SubsetSumZero , Учитывая решение экземпляра SubsetSumPositive, добавление − T дает решение экземпляра SubsetSumZero. И наоборот, учитывая решение экземпляра SubsetSumZero, оно должно содержать − T (поскольку все целые числа в S положительны), поэтому, чтобы получить нулевую сумму, оно также должно содержать подмножество S с суммой + T , что является решением экземпляра SubsetSumPositive.
Входные целые числа являются положительными и T = sum( S )/2. Это можно доказать и редукцией от общего варианта; см. проблему с разделом .

Аналогичная задача подсчета #SSP, которая требует подсчитать количество подмножеств, суммирующихся с целью, является #P-complete . ^[4]

времени экспоненциального Алгоритмы

Существует несколько способов решения SSP в экспоненциальном времени от n . ^[5]

Включение-исключение [ править ]

Самый наивный алгоритм — перебрать все подмножества из n чисел и для каждого из них проверить, равна ли сумма подмножества правильному числу. Время работы в порядке $O(2^{n}\cdot n)$ , поскольку есть $2^{n}$ подмножества, и для проверки каждого подмножества нам нужно суммировать не более n элементов.

Алгоритм может быть реализован путем поиска в глубину двоичного дерева: каждый уровень в дереве соответствует входному номеру; левая ветвь соответствует исключению числа из множества, а правая ветвь соответствует включению числа (отсюда и название Включение-Исключение). Требуемый объем памяти $O(n)$ . Время выполнения можно улучшить с помощью нескольких эвристик: ^[5]

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

Горовиц и Сахни [ править ]

В 1974 году Горовиц и Сахни ^[6] опубликовал более быстрый алгоритм экспоненциального времени, который работает во времени $O(2^{n/2}\cdot (n/2))$ , но требует гораздо больше места - $O(2^{n/2})$ . Алгоритм произвольно разбивает n элементов на два набора $n/2$ каждый. Для каждого из этих двух наборов он хранит список сумм всех $2^{n/2}$ возможные подмножества его элементов. Затем каждый из этих двух списков сортируется. Даже при использовании самого быстрого алгоритма сортировки сравнением сортировка слиянием на этом этапе потребует времени. $O(2^{n/2}n)$ . Однако, учитывая отсортированный список сумм для $k$ элементов список можно расширить до двух отсортированных списков с помощью ( $k+1$ )-й элемент, и эти два отсортированных списка можно объединить во времени. $O(2^{k})$ . Таким образом, каждый список может быть сгенерирован в отсортированном по времени виде. $O(2^{n/2})$ . Учитывая два отсортированных списка, алгоритм может проверить, равна ли сумма элемента первого массива и элемента второго массива T за время. $O(2^{n/2})$ . Для этого алгоритм проходит через первый массив в порядке убывания (начиная с наибольшего элемента) и второй массив в порядке возрастания (начиная с наименьшего элемента). Всякий раз, когда сумма текущего элемента в первом массиве и текущего элемента во втором массиве больше T , алгоритм переходит к следующему элементу в первом массиве. Если оно меньше T , алгоритм переходит к следующему элементу второго массива. два элемента, сумма которых равна T Если найдены , процесс останавливается. (Подзадача о сумме двух элементов называется двойной суммой. ^[7])

Шреппель и Шамир [ править ]

В 1981 году Шреппель и Шамир представили алгоритм. ^[8] на основе Горовица и Санхи, для этого требуется аналогичное время выполнения - $O(2^{n/2}\cdot (n/4))$ , намного меньше места - $O(2^{n/4})$ . Вместо того, чтобы генерировать и сохранять все подмножества из n заранее /2 элементов, они разделяют элементы на 4 набора по n /4 элемента каждый и динамически генерируют подмножества из n /2 пар элементов, используя минимальную кучу , что дает указанное выше время и космические сложности, поскольку это можно сделать в $O(k^{2}\log(k))$ и космос $O(k)$ дано 4 списка длины k.

Из-за требований к пространству алгоритм HS практичен для обработки примерно до 50 целых чисел, а алгоритм SS — для обработки до 100 целых чисел. ^[5]

Хогрейв-Грэм и Жу [ править ]

В 2010 году Хогрейв-Грэм и Жу ^[9] представил вероятностный алгоритм , который работает быстрее всех предыдущих — по времени $O(2^{0.337n})$ используя пространство $O(2^{0.256n})$ . Он решает только проблему решения, не может доказать отсутствие решения для данной суммы и не возвращает сумму подмножества, наиболее близкую к T .

Впоследствии методы Хогрейва-Грэма и Жу были расширены. ^[10] привнося временную сложность в $O(2^{0.291n})$ .

псевдополиномиальным для динамического программирования с Решения временем

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

x_{1},\ldots ,x_{N}

Мы определяем состояние как пару ( i , s ) целых чисел. Это состояние отражает тот факт, что

"есть непустое подмножество

x_{1},\ldots ,x_{i}

что в сумме равно

s

».

Каждое состояние ( i , s ) имеет два следующих состояния:

( i +1, s ), подразумевая, что $x_{i+1}$ не входит в подмножество;
( я +1, с + $x_{i+1}$ ), подразумевая, что $x_{i+1}$ входит в подмножество.

Начиная с начального состояния (0, 0), можно использовать любой алгоритм поиска по графу (например, BFS ) для поиска состояния ( N , T ). возвращаясь назад, мы можем найти подмножество с суммой ровно T. Если состояние найдено, то ,

Время выполнения этого алгоритма не более чем линейно по числу состояний. Число состояний не более чем в N раз превышает количество различных возможных сумм. Пусть $A$ будет суммой отрицательных значений, а $B$ - суммой положительных значений; количество различных возможных сумм не превышает B – A , поэтому общее время выполнения находится в $O(N(B-A))$ . Например, если все входные значения положительны и ограничены некоторой константой C , то B не превышает NC , поэтому требуемое время равно $O(N^{2}C)$ .

Это решение не считается полиномиальным временем в теории сложности, потому что $B-A$ не является полиномиальным по размеру задачи, то есть количеству битов, используемых для ее представления. Этот алгоритм является полиномиальным по значениям $A$ и $B$ , которые являются экспоненциальными по числу битов. Однако сумма подмножества, закодированная в унарном формате, находится в P, поскольку тогда размер кодирования является линейным в BA. Следовательно, Subset Sum лишь слабо NP-полна.

Для случая, когда каждый $x_{i}$ положителен и ограничен фиксированной константой $C$ , в 1999 году Пизингер нашел алгоритм с линейным временем, имеющий временную сложность $O(NC)$ (обратите внимание, что это относится к той версии задачи, в которой целевая сумма не обязательно равна нулю, иначе проблема была бы тривиальной). ^[11] В 2015 году Койлиарис и Сюй нашли детерминистический подход. ${\tilde {O}}(T{\sqrt {N}})$ алгоритм решения задачи о сумме подмножеств, где $T$ — сумма, которую нам нужно найти. ^[12] В 2017 году Брингманн обнаружил рандомизированное исследование. ${\tilde {O}}(T+N)$ временной алгоритм. ^[13]

В 2014 году Кертис и Санчес нашли простую рекурсию, хорошо масштабируемую на SIMD -машинах, имеющую $O(N(m-x_{\min })/p)$ время и $O(N+m-x_{\min })$ пространство, где $p$ — количество обрабатывающих элементов, $m=\min(s,\sum x_{i}-s)$ и $x_{\min }$ является наименьшим целым числом. ^[14] Это лучшая теоретическая параллельная сложность, известная на данный момент.

Сравнение практических результатов и решение сложных случаев SSP обсуждается Кертисом и Санчесом. ^[15]

времени аппроксимации Алгоритмы полиномиального

Предположим, что все входные данные положительны. Алгоритм аппроксимации SSP направлен на поиск подмножества S с суммой не более T и по меньшей мере в r раз большей оптимальной суммы, где r - число в (0,1), называемое коэффициентом аппроксимации .

Простое 1/2-приближение [ править ]

Следующий очень простой алгоритм имеет коэффициент аппроксимации 1/2: ^[16]

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

Когда этот алгоритм завершает работу, либо все входные данные находятся в подмножестве (что, очевидно, является оптимальным), либо есть входные данные, которые не подходят. Первый такой входной сигнал меньше, чем все предыдущие входные данные, находящиеся в подмножестве, а сумма входных данных в подмножестве больше T /2, в противном случае входной сигнал также меньше T/2 и он бы поместился в набор. Такая сумма, превышающая T/2, очевидно, больше OPT/2.

Полностью полиномиальная схема времени аппроксимации

Следующий алгоритм достигает для каждого $\epsilon >0$ , коэффициент аппроксимации $(1-\epsilon )$ . Время его выполнения полиномиально от $n$ и $1/\epsilon$ . Напомним, что n — количество входных данных, а T — верхняя граница суммы подмножества.

initialize a list L to contain one element 0.

for each i from 1 to n do
    let U_i be a list containing all elements y in L, and all sums x_i + y for all y in L.
    sort U_i in ascending order
    make L empty 
    let y be the smallest element of U_i
    add y to L
    for each element z of U_i in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

Обратите внимание, что без шага обрезки (внутренний цикл «для каждого») список L будет содержать суммы всех $2^{n}$ подмножества входов. Этап обрезки выполняет две задачи:

Это гарантирует, что все суммы, оставшиеся в L , ниже T , поэтому они являются допустимыми решениями проблемы суммы подмножества.
Это гарантирует, что список L является «разреженным», то есть разница между каждыми двумя последовательными частичными суммами составляет не менее $\epsilon T/n$ .

Вместе эти свойства гарантируют, что список $L$ содержит не более $n/\epsilon$ элементы; поэтому время выполнения является полиномиальным по $n/\epsilon$ .

Когда алгоритм завершается, если оптимальная сумма находится в $L$ , она возвращается, и все готово. В противном случае он должен был быть удален на предыдущем этапе обрезки. Каждый шаг обрезки вносит аддитивную ошибку не более $\epsilon T/n$ , поэтому $n$ шагов вместе вносят ошибку не более $\epsilon T$ . Следовательно, возвращаемое решение не менее ${\text{OPT}}-\epsilon T$ что по крайней мере $(1-\epsilon ){\text{OPT}}$ .

Приведенный выше алгоритм обеспечивает точное решение SSP в случае, когда входные числа малы (и неотрицательны). Если любую сумму чисел можно задать не более чем $P$ битами, то решение задачи приближенно с $\epsilon =2^{-P}$ эквивалентно ее точному решению. Тогда алгоритм с полиномиальным временем для приближенной суммы подмножества становится точным алгоритмом с полиномиальным временем выполнения от $n$ и $2^{P}$ (т. е. экспоненциально по $P$ ).

Келлерер, Мансини, Пферши и Сперанца. ^[17] и Келлерер, Пферши и Пизингер ^[18] представить другие FPTAS-ы для суммы подмножества.

См. также [ править ]

Задача о рюкзаке - задача комбинаторной оптимизации - обобщение SSP, в котором каждый входной элемент имеет как значение, так и вес. Цель состоит в том, чтобы максимизировать значение с учетом ограничения общего веса .
Задача о сумме нескольких подмножеств - обобщение SSP, в котором нужно выбрать несколько подмножеств.
3SUM - Задача теории сложности вычислений
Ранцевая криптосистема Меркла-Хеллмана - одна из первых криптосистем с открытым ключом, изобретенная Ральфом Мерклем и Мартином Хеллманом в 1978 году. Идеи, лежащие в ее основе, проще, чем идеи, связанные с RSA, и она сломана.

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). п. 491 . ISBN 0-321-37291-3 .
^ Гудрич, Майкл. «Больше полных и сложных задач NP» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . , раздел 3.1 и задача SP1 в Приложении А.3.1.
↑ Filmus, Юваль (30 января 2016 г.). Ответ на вопрос: « Существует ли известный быстрый алгоритм подсчета всех подмножеств, сумма которых меньше определенного числа? ». теоретической информатики Обмен стеками . Обратите внимание, что цитата Filmus в поддержку этого утверждения (Faliszewski, Piotr; Hemaspaandra, Lane (2009). «Сложность сравнения показателей мощности». Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs .2008.09.034 ) на самом деле не доказывает это утверждение, вместо этого направляя читателей к другой цитате ( Papadimitriou, Christos (1994). Computational Complexity . Addison-Wesley: Reading, MA. Глава 9. ISBN 0-201-53082-1 — через Интернет-архив ), что также не доказывает это утверждение явно. Однако доказательство Пападимитриу того, что SSP является NP-полным посредством редукции 3SAT , обобщается до редукции от #3SAT до #SSP.
^ Jump up to: Перейти обратно: ^а ^б ^с Ричард Э. Корф, Итан Л. Шрайбер и Майкл Д. Моффит (2014). «Оптимальное последовательное многостороннее разделение номеров» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Горовиц, Эллис; Сахни, Сартадж (1974). «Расчет разделов с приложениями к задаче о рюкзаке» (PDF) . Журнал Ассоциации вычислительной техники . 21 (2): 277–292. дои : 10.1145/321812.321823 . hdl : 1813/5989 . МР 0354006 . S2CID 16866858 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ «Задача двух сумм» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Шреппель, Ричард; Шамир, Ади (1 августа 1981 г.). «А $Т = О (2 н /2)$ , $S = О (2 н /4)$ алгоритм для некоторых NP-полных задач» . SIAM Journal on Computing . 10 (3): 456–464. doi : 10.1137/0210033 . ISSN 0097-5397 .
^ Хоугрейв-Грэм, Ник; Жу, Антуан (2010). «Новые универсальные алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. Берлин, Гейдельберг: Springer. стр. 235–256. дои : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5 .
^ Беккер, Аня; Жу, Антуан (2010). «Улучшенные общие алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2011 . Конспекты лекций по информатике. Том. 6632. Берлин, Гейдельберг: Springer. стр. 364–385. дои : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4 .
^ Пизингер, Дэвид (1999). «Алгоритмы линейного времени для задач о рюкзаке с ограниченными весами». Журнал алгоритмов . 33 (1): 1–14. дои : 10.1006/jagm.1999.1034 . МР 1712690 .
^ Койлиарис, Константинос; Сюй, Чао (08 июля 2015 г.). «Более быстрый алгоритм псевдополиномиального времени для суммы подмножества». arXiv : 1507.02318 [ cs.DS ].
^ Брингманн, Карл (2017). «Почти линейный алгоритм псевдополиномиального времени для вычисления суммы подмножества». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2017) . СИАМ. стр. 1073–1084. arXiv : 1610.04712 . дои : 10.1137/1.9781611974782.69 .
^ Кертис, В.В.; Санчес, CAA (январь 2016 г.). «Эффективное решение проблемы суммы подмножества на графическом процессоре: эффективное решение проблемы суммы подмножества на графическом процессоре». Параллелизм и вычисления: практика и опыт . 28 (1): 95–113. дои : 10.1002/cpe.3636 . S2CID 20927927 .
^ Кертис, В.В.; Санчес, CAA (июль 2017 г.). «Алгоритм с малым пространством для решения проблемы суммы подмножества на графическом процессоре». Компьютеры и исследования операций . 83 : 120–124. дои : 10.1016/j.cor.2017.02.006 .
^ Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 февраля 2000 г.). «Проблема суммы множественных подмножеств» . SIAM Journal по оптимизации . 11 (2): 308–319. дои : 10.1137/S1052623498348481 . ISSN 1052-6234 .
^ Келлерер, Ганс; Мансини, Рената; Пферши, Ульрих; Сперанца, Мария Грация (01 марта 2003 г.). «Эффективная полностью полиномиальная схема аппроксимации для задачи о сумме подмножеств». Журнал компьютерных и системных наук . 66 (2): 349–370. дои : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .
^ Ганс Келлерер; Ульрих Пферши; Дэвид Пизингер (2004). Проблемы с рюкзаком . Спрингер. п. 97. ИСБН 9783540402862 .

Дальнейшее чтение [ править ]

Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «35.5: Проблема суммы подмножества». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 .
Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0-7167-1045-5 . А3.2: СП13, стр.223.
Лагариас, JC; Одлизко, А. М. (1 января 1985 г.). «Решение задач о сумме подмножеств низкой плотности» . Журнал АКМ . 32 (1): 229–246. дои : 10.1145/2455.2461 . ISSN 0004-5411 . S2CID 885632 .
Мартелло, Сильвано; Тот, Паоло (1990). «4 Проблема суммы подмножества» . Задачи о рюкзаке: Алгоритмы и компьютерные интерпретации . Уайли-Интерсайенс. стр. 105–136 . ISBN 0-471-92420-2 . МР 1086874 .

[kleinberg2006p491-1] Jump up to: Перейти обратно: ^а ^б Кляйнберг, Джон; Тардос, Ева (2006). Разработка алгоритмов (2-е изд.). п. 491 . ISBN 0-321-37291-3 .

[2] Гудрич, Майкл. «Больше полных и сложных задач NP» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.

[garey79-3] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . , раздел 3.1 и задача SP1 в Приложении А.3.1.

[4] Filmus, Юваль (30 января 2016 г.). Ответ на вопрос: « Существует ли известный быстрый алгоритм подсчета всех подмножеств, сумма которых меньше определенного числа? ». теоретической информатики Обмен стеками . Обратите внимание, что цитата Filmus в поддержку этого утверждения (Faliszewski, Piotr; Hemaspaandra, Lane (2009). «Сложность сравнения показателей мощности». Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs .2008.09.034 ) на самом деле не доказывает это утверждение, вместо этого направляя читателей к другой цитате ( Papadimitriou, Christos (1994). Computational Complexity . Addison-Wesley: Reading, MA. Глава 9. ISBN 0-201-53082-1 — через Интернет-архив ), что также не доказывает это утверждение явно. Однако доказательство Пападимитриу того, что SSP является NP-полным посредством редукции 3SAT , обобщается до редукции от #3SAT до #SSP.

[:0-5] Jump up to: Перейти обратно: ^а ^б ^с Ричард Э. Корф, Итан Л. Шрайбер и Майкл Д. Моффит (2014). «Оптимальное последовательное многостороннее разделение номеров» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[6] Горовиц, Эллис; Сахни, Сартадж (1974). «Расчет разделов с приложениями к задаче о рюкзаке» (PDF) . Журнал Ассоциации вычислительной техники . 21 (2): 277–292. дои : 10.1145/321812.321823 . hdl : 1813/5989 . МР 0354006 . S2CID 16866858 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[7] «Задача двух сумм» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.

[8] Шреппель, Ричард; Шамир, Ади (1 августа 1981 г.). «А $Т = О (2 н /2)$ , $S = О (2 н /4)$ алгоритм для некоторых NP-полных задач» . SIAM Journal on Computing . 10 (3): 456–464. doi : 10.1137/0210033 . ISSN 0097-5397 .

[9] Хоугрейв-Грэм, Ник; Жу, Антуан (2010). «Новые универсальные алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. Берлин, Гейдельберг: Springer. стр. 235–256. дои : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5 .

[10] Беккер, Аня; Жу, Антуан (2010). «Улучшенные общие алгоритмы для твердых рюкзаков». В Гилберте, Анри (ред.). Достижения в криптологии – EUROCRYPT 2011 . Конспекты лекций по информатике. Том. 6632. Берлин, Гейдельберг: Springer. стр. 364–385. дои : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4 .

[Pisinger09-11] Пизингер, Дэвид (1999). «Алгоритмы линейного времени для задач о рюкзаке с ограниченными весами». Журнал алгоритмов . 33 (1): 1–14. дои : 10.1006/jagm.1999.1034 . МР 1712690 .

[12] Койлиарис, Константинос; Сюй, Чао (08 июля 2015 г.). «Более быстрый алгоритм псевдополиномиального времени для суммы подмножества». arXiv : 1507.02318 [ cs.DS ].

[13] Брингманн, Карл (2017). «Почти линейный алгоритм псевдополиномиального времени для вычисления суммы подмножества». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2017) . СИАМ. стр. 1073–1084. arXiv : 1610.04712 . дои : 10.1137/1.9781611974782.69 .

[14] Кертис, В.В.; Санчес, CAA (январь 2016 г.). «Эффективное решение проблемы суммы подмножества на графическом процессоре: эффективное решение проблемы суммы подмножества на графическом процессоре». Параллелизм и вычисления: практика и опыт . 28 (1): 95–113. дои : 10.1002/cpe.3636 . S2CID 20927927 .

[15] Кертис, В.В.; Санчес, CAA (июль 2017 г.). «Алгоритм с малым пространством для решения проблемы суммы подмножества на графическом процессоре». Компьютеры и исследования операций . 83 : 120–124. дои : 10.1016/j.cor.2017.02.006 .

[:1-16] Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 февраля 2000 г.). «Проблема суммы множественных подмножеств» . SIAM Journal по оптимизации . 11 (2): 308–319. дои : 10.1137/S1052623498348481 . ISSN 1052-6234 .

[17] Келлерер, Ганс; Мансини, Рената; Пферши, Ульрих; Сперанца, Мария Грация (01 марта 2003 г.). «Эффективная полностью полиномиальная схема аппроксимации для задачи о сумме подмножеств». Журнал компьютерных и системных наук . 66 (2): 349–370. дои : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .

[knapsack-18] Ганс Келлерер; Ульрих Пферши; Дэвид Пизингер (2004). Проблемы с рюкзаком . Спрингер. п. 97. ИСБН 9783540402862 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]