Числовое трехмерное сопоставление

Численное трехмерное сопоставление представляет собой NP-полную задачу решения. Он задается тремя мультимножествами целых чисел $X$ , $Y$ и $Z$ , каждый из которых содержит $k$ элементы и граница $b$ . Цель состоит в том, чтобы выбрать подмножество $M$ из $X\times Y\times Z$ такая, что каждое целое число в $X$ , $Y$ и $Z$ происходит ровно один раз и то для каждой тройки $(x,y,z)$ в подмножестве $x+y+z=b$ держит.Эта проблема обозначена как [SP16]. ^[1]

Пример

Брать $X=\{3,4,4\}$ , $Y=\{1,4,6\}$ и $Z=\{1,2,5\}$ , и $b=10$ . Этот пример имеет решение, а именно $\{(3,6,1),(4,4,2),(4,1,5)\}$ . Обратите внимание, что сумма каждой тройки равна $b=10$ . Набор $\{(3,6,1),(3,4,2),(4,1,5)\}$ не является решением по нескольким причинам: используется не каждое число ( $4\in X$ отсутствует), число используется слишком часто (значок $3\in X$ ) и не каждая тройная сумма равна $b$ (с $3+4+2=9\neq b=10$ ). Однако есть по крайней мере одно решение этой проблемы, и это то свойство, которое нас интересует в задачах решения.Если бы мы взяли $b=11$ для того же самого $X$ , $Y$ и $Z$ , эта задача не имеет решения (сумма всех чисел равна $30$ , что не равно $k\cdot b=33$ в этом случае).

Связанные проблемы

Каждый экземпляр задачи численного трехмерного сопоставления является одновременно и задачей трехмерного сопоставления , и задачей трехмерного сопоставления .

Учитывая пример числового 3D-сопоставления, постройте трехсторонний гиперграф со сторонами $X$ , $Y$ и $Z$ , где есть гиперребро ⁠ $(x,y,z)$ ⁠ тогда и только тогда, когда $x+y+z=T$ . Паросочетание в этом гиперграфе соответствует решению ABC-разбиения.

Доказательство NP-полноты

Задача численного трехмерного сопоставления — это задача [SP16] Гари и Джонсона. ^[1] Они утверждают, что он NP-полн, и ссылаются на: ^[2] но утверждение не доказано в этом источнике. NP-трудность связанной задачи с 3-разбиениями выполняется в ^[1] за счет сокращения трехмерного сопоставления с помощью 4-разделов. Чтобы доказать NP-полноту численного трехмерного сопоставления, доказательство должно быть аналогичным, но следует использовать сокращение от трехмерного сопоставления с помощью численной задачи четырехмерного сопоставления. Явные доказательства NP-твердости приведены в более поздних работах:

Ю, Хугевен и Ленстра ^[3] доказать NP-трудность очень ограниченной версии числового трехмерного сопоставления, в которой два из трех наборов содержат только числа 1,..., k.
Караччоло, Фичера и Спортиелло ^[4] доказать NP-трудность численного трехмерного сопоставления и связанных с ним проблем путем сокращения из NAE-SAT . Уменьшение является линейным , то есть размер уменьшенного экземпляра является линейной функцией размера исходного экземпляра.

Ссылки

^ Jump up to: ^а ^б ^с Гэри, Майкл Р. и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы; Руководство по теории NP-полноты. ISBN 0-7167-1045-5
^ Гэри, MR; Джонсон, DS (декабрь 1975 г.). «Результаты сложности многопроцессорного планирования в условиях ограничений ресурсов» . SIAM Journal по вычислительной технике . 4 (4): 397–411. дои : 10.1137/0204035 . ISSN 0097-5397 .
^ Ю, Венчи; Хугевен, Хан; Ленстра, Ян Карел (1 сентября 2004 г.). «Минимизация периода ремонта в двухмашинном цехе с задержками и единичными операциями является NP-сложной задачей» . Журнал планирования . 7 (5): 333–348. дои : 10.1023/B:JOSH.0000036858.59787.c2 . ISSN 1099-1425 .
^ Караччоло, Серджио; Фичера, Давиде; Спортиелло, Андреа (28 апреля 2006 г.), Задача сопоставления «один из двух» NP-полна , arXiv : cs/0604113 , Bibcode : 2006cs........4113C

[garey-1] Jump up to: ^а ^б ^с Гэри, Майкл Р. и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы; Руководство по теории NP-полноты. ISBN 0-7167-1045-5

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

[3] Ю, Венчи; Хугевен, Хан; Ленстра, Ян Карел (1 сентября 2004 г.). «Минимизация периода ремонта в двухмашинном цехе с задержками и единичными операциями является NP-сложной задачей» . Журнал планирования . 7 (5): 333–348. дои : 10.1023/B:JOSH.0000036858.59787.c2 . ISSN 1099-1425 .

[4] Караччоло, Серджио; Фичера, Давиде; Спортиелло, Андреа (28 апреля 2006 г.), Задача сопоставления «один из двух» NP-полна , arXiv : cs/0604113 , Bibcode : 2006cs........4113C

[1]

[2]

[3]

[4]