Проблема с 3 разделами

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

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

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

Пример

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

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

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

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

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

Варианты

В варианте с неограниченным входом входы могут быть произвольными целыми числами; в варианте с ограниченным входом входы должны быть в ( T /4 , T /2). Ограниченная версия так же сложна, как и неограниченная версия: учитывая экземпляр S _u неограниченного варианта, построить новый экземпляр ограниченной версии S _r ≔ {s + 2  T   | s ∈ S _u }. Каждое решение S _u соответствует решению 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 ∈ S _r }, с 3m элементами, дающими в сумме 7mT , и с целевой суммой 7  T  . Каждое решение S _r естественным образом соответствует решению S _u . Наоборот, в каждом решении S _u , поскольку целевая сумма равна 7  T   , а каждый элемент находится в ( T  /4, 7  T  /2 )  , должно быть ровно 3 элемента на набор, поэтому он соответствует решению S _r .

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

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

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

Гари и Джонсон (1975) первоначально доказали, что 3-разбиение является NP-полным, путем сведения от 3-мерного сопоставления . ^[3] Классический источник Гари и Джонсона (1979) описывает доказательство NP-полноты, сводящееся от 3-мерного сопоставления к 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 ⁴ -kr ³ -jr ² -ir.
• Для каждого триплета 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") как "реальный", а другие как "фиктивные". Размеры элементов следующие:
  • w _i [1] = 10r ⁴ +ir; w _i [2..] = 11r ⁴ +ir.
  • x _j [1] = 10r ⁴ +jr ² ; x _j [2..] = 11r ⁴ +jr ² .
  • y _k [1] = 10r ⁴ +kr ³ ; y _k [2..] знак равно 8r ⁴ +kr ³ .
• Сумма каждых трех «реальных» элементов или каждых трех «фиктивных» элементов равна 30r ⁴ +ir+jr ² +kr ³ ; а если добавить элемент триплета, то сумма составит 40r ⁴ .
• Порог для экземпляра ABCD-partition равен T=40r ^4. Обратите внимание, что размер каждого элемента находится в диапазоне (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-сета составляет 40r ⁴ по мере необходимости.

Учитывая разбиение ABCD, сумма каждого 4-множества равна 40r ⁴ . Следовательно, члены с r, r ² и r ³ должны сократиться, а члены с r ⁴ должны в сумме дать 40r ⁴ ; поэтому 4-множество должно содержать триплет и 3 соответствующих «реальных» элемента или триплет и 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.

В итоге сумма составляет 16mT+15m, а новый порог — 16T+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 m регулярных элементов, что в сумме составляет 81mT + 4m.
• Для каждой пары элементов a _i ,a _j в A, B содержит два «спаренных» элемента: u _ij = 4*(6T - a _i - a _j )+2 и u _ij ' = 4*(5T + a _i + a _j )+2. Всего имеется 4 m* (4 m -1) парных элементов, что в сумме дает (88mT+16m)*(4 m -1).
• Кроме того, B содержит 8м ² -3м «заполняющих» элементов размером 20T, а общая сумма составляет (8м ² -3м)*20T.
• Всего B содержит 24m ² -3m = 3(8m ² -m) элементов, с суммой (64T+4)*(8m ² -m).
• Пороговое значение для экземпляра с тремя разделами составляет 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 ₄ +5T+a ₁ +a ₂ )+1+1+2=64T+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 разбито на 3 части, то сумма каждого набора из 3 элементов кратна 4, поэтому он должен содержать либо два обычных элемента и один элемент сопряжения, либо два элемента сопряжения и один элемент-заполнитель:

• Если набор из 3 элементов содержит два элемента для сопряжения u _ij , _ukl и один элемент-заполнитель, то сумма двух элементов для сопряжения должна быть 44T+4 = 4*(5T+6T)+2+2, поэтому они должны иметь совпадающие размеры (a _i +a _j =a _k +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]

Ссылки

1. Хьюлетт, Хизер; Уилл, Тодд Г.; Вёгингер, Герхард Дж. (01.09.2008). «Мультиграфовые реализации степенных последовательностей: максимизация проста, минимизация сложна». Operations Research Letters . 36 (5): 594–596. doi :10.1016/j.orl.2008.05.004. ISSN  0167-6377.
2. Демейн, Эрик (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I". Youtube . Архивировано из оригинала 2021-12-14.
3. Garey, Michael R. и David S. Johnson (1975). «Результаты сложности для многопроцессорного планирования при ограничениях ресурсов». SIAM Journal on Computing . 4 (4): 397–411. doi :10.1137/0204035.
4. Гэри, Майкл Р. и Дэвид С. Джонсон (1979), Компьютеры и неразрешимость; Руководство по теории NP-полноты . ISBN 0-7167-1045-5 . Страницы 96–105 и 224. 
5. "Тетрис сложен, даже приблизиться к нему". Nature . 2002-10-28. doi :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. Демейн, Эрик Д.; Демейн, Мартин Л. (2007-06-01). «Головоломки, сопоставление рёбер и упаковка полимино: связи и сложность». Графы и комбинаторика . 23 (S1): 195–208. doi :10.1007/s00373-007-0713-4. ISSN  0911-0119. S2CID  17190810.
8. Бернстайн, Д.; Родех, М.; Гертнер, И. (1989). «О сложности задач планирования для параллельных/конвейерных машин». IEEE Transactions on Computers . 38 (9): 1308–1313. doi :10.1109/12.29469. ISSN  0018-9340.