проблема с тремя разделами

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

Входные данные: мультимножество S, содержащее n положительных целых элементов.
Условия: S должно быть разделено на m троек, S ₁ , S ₂ , …, S _m , где n = 3m . Эти тройки разбивают S в том смысле, что они не пересекаются и покрывают S . Целевое значение T вычисляется путем взятия суммы всех элементов в S , а затем деления на m .
Выход: существует ли такое разбиение S , что для всех троек сумма элементов в каждой тройке равна T .

Проблема трех разбиений остается строго NP-полной при условии, что каждое целое число в S находится строго между T /4 и T /2.

Пример

Набор $S=\{20,23,25,30,49,45,27,30,30,40,22,19\}$ можно разделить на четыре набора $\{20,25,45\},\{23,27,40\},\{49,22,19\},\{30,30,30\}$ , сумма каждого из которых равна T = 90.
Набор $S=\{1,2,5,6,7,9\}$ можно разделить на два набора $\{1,5,9\},\{2,6,7\}$ сумма каждого из которых равна Т = 15.
(каждое целое число в S находится строго между T /4 и T /2): $S=\{4,5,5,5,5,6\}$ , таким образом, m =2 и T =15. Возможен 3-раздельный $\{4,5,6\},\{5,5,5\}$ .
(каждое целое число в S находится строго между T /4 и T /2): $S=\{4,4,4,6,6,6\}$ , таким образом, m =2 и T =15. Решения нет.

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

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

3-раздел против раздела

Проблема с тремя разделами аналогична задаче разделения , в которой цель состоит в том, чтобы разделить S на два подмножества с одинаковой суммой, и многостороннему числовому разделению , в котором цель состоит в том, чтобы разделить S на k подмножеств с одинаковой суммой, где k является фиксированным параметром. В 3-разделении цель состоит в том, чтобы разделить S на m = n /3 подмножества, а не просто на фиксированное количество подмножеств, с одинаковой суммой. Раздел «проще», чем 3-раздел: в то время как 3-раздел является сильно NP-сложным , Раздел лишь слабо NP-сложный — он сложен только тогда, когда числа закодированы в неунарной системе и имеют экспоненциальное значение по n . Когда значения являются полиномиальными по n , разделение может быть решено за полиномиальное время с использованием алгоритма разделения чисел псевдополиномиального времени .

Варианты

В варианте с неограниченным вводом входные данные могут быть произвольными целыми числами; в варианте с ограниченным входом входы должны быть в ( T /4 , T /2). Ограниченная версия так же сложна, как и неограниченная: по заданному экземпляру S _u неограниченного варианта создайте новый экземпляр ограниченной версии $S r ≔ {s + 2 T | s \in S u$ }. Каждое решение Su _{, и} соответствует решению S _r , но с суммой 7 T вместо T каждый элемент S _r находится в [2 T , 3 T ] , который содержится в ( T /4, 7 T / 2 ) .

В варианте с отдельным входом входные данные должны быть в ( T /4 , T /2 ), и, кроме того, все они должны быть различными целыми числами. Это также так же сложно, как и неограниченная версия. ^[1]

В варианте с неограниченным выходом выходных подмножеств m могут иметь произвольный размер — не обязательно 3 (но они все равно должны иметь одинаковую сумму T ). Вариант с ограниченным выходом можно свести к варианту с неограниченным выходом: учитывая экземпляр S _r ограниченного варианта с 3 m элементами, сумма которых равна mT , построить новый экземпляр неограниченного варианта $S u ≔ {s + 2 T | s \in S r$ }, с 3m элементами в сумме до 7mT и с целевой суммой 7 T . решение Sr _{естественно} соответствует решению Su _Каждое . И наоборот, в каждом решении , _Su поскольку целевая сумма равна 7 T и каждый элемент находится в ( T /4, 7 T /2 ) , в каждом наборе должно быть ровно 3 элемента, поэтому это соответствует решению S _r .

Задача ABC -разбиения (также называемая числовым трехмерным сопоставлением ) — это вариант, в котором вместо набора S с 3 m целыми числами есть три набора A , B , C с m целыми числами в каждом. Сумма чисел во всех наборах равна ⁠ $mT$ ⁠ . Цель состоит в том, чтобы построить m троек, каждая из которых содержит один элемент из A, один из B и один из C, так что сумма каждой тройки равна T . ^[2]

Задача о 4-х разделах — это вариант, в котором S содержит n = 4 m целых чисел, сумма всех целых чисел равна ⁠ $mT$ ⁠ , и цель состоит в том, чтобы разбить его на m четверок, все с суммой T . Можно предположить, что каждое целое число находится строго между T /5 и T /3. Аналогично, ABCD-парититон — это вариант 4-разбиения, в котором каждый имеет 4 входных набора, и каждый четверка должна содержать по одному элементу из каждого набора.

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

Гари и Джонсон (1975) первоначально доказали, что 3-разделение является NP-полным, путем сокращения трехмерного сопоставления . ^[3] Классическая ссылка Гари и Джонсона (1979) описывает доказательство NP-полноты, сводящееся от трехмерного сопоставления к 4-разбиению и 3-разделению. ^[4] Логически сокращение можно разбить на несколько этапов.

Приведение от 3d-сопоставления к ABCD-разбиению

Нам дан экземпляр E 3d-сочетания, содержащий несколько m троек {w _i ,x _j ,y _k }, где вершинами являются w ₁ ,...,w _q и x ₁ ,...,x _q и y ₁ ,...,y _q . Мы создаем экземпляр ABCD-раздела с 4* m элементами следующим образом (где r := 32q):

Для каждой тройки t = {w _i ,x _j ,y _k } в E множество A содержит элемент u _t = 10r ⁴- НОК ³-младший ²-и.
Для каждой тройки t = {w _i ,x _j ,y _k } в E множество B содержит w _it , C содержит x _jt , а D содержит y _kt . Таким образом, для каждого из w _i , x _j , y _k может существовать множество соответствующих элементов в B, C, D — по одному на каждую тройку, в которой они появляются. Считаем один из этих элементов (обозначаемый цифрой «1») «настоящим», а остальные — «фиктивными». Размеры элементов следующие:
- ш _я [1] = 10р ⁴+ир; ш _я [2..] = 11р ⁴+ и
- х _j [1] = 10р ⁴+младший ²; х _j [2..] = 11р ⁴+младший ².
- ук _10р [1] = ⁴+кр ³; y _k [2..] = 8r ⁴+кр ³.
Сумма каждых трёх «настоящих» элементов или каждых трёх «фиктивных» элементов равна 30р. ⁴+ир+младший ²+кр ³; а если добавить тройной элемент, то сумма составит 40р ⁴.
Порог для экземпляра ABCD-раздела равен T=40r. ⁴. Обратите внимание, что размер каждого элемента указан в (T/3,T/5).

Учитывая идеальное паросочетание в E , мы строим 4-разбиение ABCD следующим образом:

Для каждой тройки t= { w _i ,x _j ,y _k } в паросочетании мы строим 4-множество {u _t , w _i [1], x _j [1], y _k [1]}.
Для каждой тройки, не входящей в паросочетание, строим аналогичное 4-множество, но с соответствующими фиктивными элементами.

В обоих случаях сумма 4-сета равна 40р. ⁴ по мере необходимости.

Учитывая разбиение ABCD, сумма каждой четверки равна 40r. ⁴. Следовательно, члены с r, r ² и р ³ должны сокращаться, и члены с r ⁴ должна получить сумму до 40р ⁴; поэтому набор из 4 должен содержать тройку и 3 совпадающих «настоящих» элемента или тройку и 3 совпадающих «фиктивных» элемента. Из троек с тремя совпадающими «реальными» элементами мы строим действительное совершенное паросочетание в E.

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

Сокращение от ABCD-раздела до 4-х разделов

Учитывая экземпляр ABCD-раздела с m элементами в наборе, порогом T и суммой mT , мы создаем экземпляр 4-раздела с 4 m элементами:

Для каждого элемента a в A соответствующий элемент имеет размер 16a+1;
Для каждого элемента b в B соответствующий элемент имеет размер 16b+2;
Для каждого элемента c в C соответствующий элемент имеет размер 16c+4;
Для каждого элемента d в D соответствующий элемент имеет размер 16d+8.

В целом сумма составляет 16т+15м, а новый порог — 16т+15.

Каждому ABCD-разбиению естественным образом соответствует 4-разбиение. И наоборот, в каждом 4-разделе сумма по модулю 16 равна 15, и поэтому она должна содержать ровно один элемент с размером по модулю 16 = 1, 2, 4, 8; это соответствует ровно одному элементу из A, B, C, D, из которого мы можем построить ABCD-разбиение.

Используя аналогичное сокращение, ABC-раздел можно уменьшить до 3-х разделов.

Сокращение с 4-х разделов до 3-х разделов

Нам дан экземпляр A из 4-х разделов: 4 m целых чисел, a ₁ ,...,a _4m , каждое из которых находится в диапазоне (T/3,T/5), сумма которых равна mT . Мы создаем экземпляр B 3-раздела следующим образом:

Для каждого a _i в A B содержит «регулярный» элемент w _i = 4*(5T+a _i )+1. Всего регулярных элементов 4 м , что в сумме дает 81мТ + 4м.
Для каждой пары элементов a _i ,a _j в A, B содержит два «парных» элемента: u _ij = 4*(6T - a _i - a _j )+2 и u _ij ' = 4*(5T + a _i + а _j )+2. Всего имеется 4 м* (4 м -1) элементов спаривания, что в сумме дает (88mT+16m)*(4 м -1).
Кроме того, B содержит 8m ²-3м элементов «наполнителя» размером 20Т и общей суммой (8м ²-3м)*20Т.
Всего в B содержится 24m. ²-3м = 3(8м ²-m) элементов с суммой (64T+4)*(8m ²-м).
Порог для экземпляра с тремя разделами — 64T+4; обратите внимание, что размеры всех элементов в B указаны в (16T+1,32T+2).

Учитывая 4-разделение A , мы строим 3-разделение для B следующим образом:

Для каждого 4-множества {a ₁ ,a ₂ ,a ₃ ,a ₄ } с суммой T построим 3-множество {w ₁ ,w ₂ ,u ₁₂ } с суммой 4*(5T+a ₁ +5T+ a ₂ +6T-a ₁ -a ₂ )+1+1+2=64T+4 и еще один набор из 3 {w ₃ ,w ₄ ,u ₁₂ '} с суммой 4*(5T+a ₃ +5T+a ₄ +5Т+а ₁ +а ₂ )+1+1+2=64Т+4. Эти наборы содержат все 4m правильных элементов и 2m совпадающих пар спаривающихся элементов.
Из оставшихся элементов построим 3-множества {u _ij ,u _ij ',filler} с суммой 4*(6T-a _i -a _j +5T+a _i +a _j +5T)+2+2=64T+ 4.

И наоборот, при трехразделах B сумма каждого набора из трех кратна 4, поэтому она должна содержать либо два обычных элемента и один парный элемент, либо два парных элемента и один элемент-заполнитель:

Если набор из трех пар содержит два парных элемента u _ij , u _kl и один элемент-заполнитель, то сумма двух парных элементов должна быть 44T+4 = 4*(5T+6T)+2+2, поэтому они должны иметь совпадение. размеры (a _i +a _j =ak ₊ a _l ). Следовательно, заменив по мере необходимости, мы можем предположить, что двумя элементами пары на самом деле являются u _ij и u _ij '. Следовательно, остальные элементы жеребьёвки также состоят из n совпадающих пар.
Следовательно, оставшиеся 3-множества можно разбить на две группы: n 3-множеств, содержащие элементы u _ij , и n 3-множества, содержащие элементы u _ij '. В каждой совпадающей паре 3-наборов сумма двух элементов пары u _ij +u _ij ' равна 44T+4, поэтому сумма четырех обычных элементов равна 84T+4. Следовательно, из четырех регулярных элементов мы строим 4-множество в A с суммой T.

Приложения

NP-твердость 3-х разделов использовалась для доказательства прямоугольной упаковки NP-твердости , а также тетриса. ^[5]^[6] и еще несколько головоломок. ^[7] и некоторые проблемы с планированием работы . ^[8]

Ссылки

^ Хьюлетт, Хизер; Уилл, Тодд Г.; Вегингер, Герхард Дж. (01 сентября 2008 г.). «Мультиграфные реализации последовательностей степеней: максимизация проста, минимизация сложна» . Письма об исследованиях операций . 36 (5): 594–596. дои : 10.1016/j.orl.2008.05.004 . ISSN 0167-6377 .
^ Демейн, Эрик (2015). «MIT OpenCourseWare — повышенная жесткость, 2–3 раздела I» . Ютуб . Архивировано из оригинала 14 декабря 2021 г.
^ Гэри, Майкл Р. и Дэвид С. Джонсон (1975). «Результаты сложности многопроцессорного планирования в условиях ограниченности ресурсов». SIAM Journal по вычислительной технике . 4 (4): 397–411. дои : 10.1137/0204035 .
^ Гэри, Майкл Р. и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы; Руководство по теории NP-полноты . ISBN 0-7167-1045-5 . Страницы 96–105 и 224.
^ «Тетрис сложно даже приблизительно оценить» . Природа . 28 октября 2002 г. дои : 10.1038/news021021-9 . ISSN 0028-0836 .
^ БРЕЙКЕЛАР, РОН; ДЕМЕЙН, ЭРИК Д.; ХОЭНБЕРГЕР, СЬЮЗАН; ХУГБУМ, ХЕНДРИК ЯН; КОСТЕРС, ВАЛЬТЕР А.; ЛИБЕН-НОВЭЛЛ, ДЭВИД (1 апреля 2004 г.). «Тетрис сложно даже приблизительно оценить» . Международный журнал вычислительной геометрии и приложений . 14 (1n02): 41–68. arXiv : cs/0210020 . дои : 10.1142/s0218195904001354 . ISSN 0218-1959 . S2CID 1177 .
^ Демейн, Эрик Д.; Демейн, Мартин Л. (1 июня 2007 г.). «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 (С1): 195–208. дои : 10.1007/s00373-007-0713-4 . ISSN 0911-0119 . S2CID 17190810 .
^ Бернштейн, Д.; Роде, М.; Гертнер, И. (1989). «О сложности задач планирования для параллельных/конвейерных машин» . Транзакции IEEE на компьютерах . 38 (9): 1308–1313. дои : 10.1109/12.29469 . ISSN 0018-9340 .

[1] Хьюлетт, Хизер; Уилл, Тодд Г.; Вегингер, Герхард Дж. (01 сентября 2008 г.). «Мультиграфные реализации последовательностей степеней: максимизация проста, минимизация сложна» . Письма об исследованиях операций . 36 (5): 594–596. дои : 10.1016/j.orl.2008.05.004 . ISSN 0167-6377 .

[2] Демейн, Эрик (2015). «MIT OpenCourseWare — повышенная жесткость, 2–3 раздела I» . Ютуб . Архивировано из оригинала 14 декабря 2021 г.

[3] Гэри, Майкл Р. и Дэвид С. Джонсон (1975). «Результаты сложности многопроцессорного планирования в условиях ограниченности ресурсов». SIAM Journal по вычислительной технике . 4 (4): 397–411. дои : 10.1137/0204035 .

[4] Гэри, Майкл Р. и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы; Руководство по теории NP-полноты . ISBN 0-7167-1045-5 . Страницы 96–105 и 224.

[5] «Тетрис сложно даже приблизительно оценить» . Природа . 28 октября 2002 г. дои : 10.1038/news021021-9 . ISSN 0028-0836 .

[6] БРЕЙКЕЛАР, РОН; ДЕМЕЙН, ЭРИК Д.; ХОЭНБЕРГЕР, СЬЮЗАН; ХУГБУМ, ХЕНДРИК ЯН; КОСТЕРС, ВАЛЬТЕР А.; ЛИБЕН-НОВЭЛЛ, ДЭВИД (1 апреля 2004 г.). «Тетрис сложно даже приблизительно оценить» . Международный журнал вычислительной геометрии и приложений . 14 (1n02): 41–68. arXiv : cs/0210020 . дои : 10.1142/s0218195904001354 . ISSN 0218-1959 . S2CID 1177 .

[7] Демейн, Эрик Д.; Демейн, Мартин Л. (1 июня 2007 г.). «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 (С1): 195–208. дои : 10.1007/s00373-007-0713-4 . ISSN 0911-0119 . S2CID 17190810 .

[8] Бернштейн, Д.; Роде, М.; Гертнер, И. (1989). «О сложности задач планирования для параллельных/конвейерных машин» . Транзакции IEEE на компьютерах . 38 (9): 1308–1313. дои : 10.1109/12.29469 . ISSN 0018-9340 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]