Вычислительная сложность задачи с 3 разделами с различными числами

Этот вопрос связан с ответом, который я разместил в ответ на другой вопрос.

Задача с 3 разделами представляет собой следующую проблему:
Экземпляр : положительные целые числа a ₁ ,…, a _n , где n = 3m, а сумма n целых чисел равна mB, так что каждый a _i удовлетворяет B / 4 <a _i <B / 2.
Вопрос : Можно ли разбить целые числа a ₁ ,…, a _n на m мультимножеств, чтобы сумма каждого мультимножества была равна B?

Хорошо известно, что задача с 3 разделами является NP-полной в строгом смысле, что она остается NP-полной, даже если числа на входе даны в унарном виде. См. Гэри и Джонсон для доказательства.

Вопросы : остается ли проблема с 3 разделами NP-полной, если числа a ₁ ,…, a _n все различны? Остаётся ли NP-полная в сильном смысле?

(Мне кажется, что ответы на оба вопроса, вероятно, да, потому что я не вижу причин, по которым проблема должна стать легче, если все числа различны.)

Похоже, что доказательство Гарея и Джонсона не устанавливает NP-полноту этой ограниченной версии.

В ответе на другой вопрос, связанный выше, я дал доказательство того, что задача с 6 разделами (определенная аналогично) с различными числами является NP-полной в сильном смысле.

cc.complexity-theory np-hardness Цуёси Ито
источник

Я думаю, что это важная проблема; В литературе я нашел несколько работ, в которых утверждается или предполагается, что заданная версия является сложной, без лучшего объяснения, чем цитата к мультимножественной версии в Garey and Johnson, и которые используют это допущение в требовании NP-полноты для какой-то другой проблемы. ,

Дэвид Эппштейн

Ответы:

$a_1, \ldots, a_n$ $B/4 < a_i < B/2$

[1]: Хизер Хьюлетт, Тодд Дж. Уилл, Герхард Дж. Вёгингер: Мультиграф реализации последовательностей степеней: максимизация проста, минимизация трудна. Опер. Местожительство Lett. 36 (5): 594-596 (2008). DOI

Серж Гасперс
источник

Наложение границ

B / 4 < a_{i} < B / 2

$B/4 < a_i < B/2$ это легко сделать, добавив одно и то же большое число ко всем

a_{i}

$a_i$ ,

Дэвид Эппштейн

Действительно, также просто навязать эти границы.

Серж Гасперс

Спасибо, он полностью отвечает на мой вопрос. Обратите внимание, что проблема частичного завершения латинского квадрата может быть легко сформулирована как частный случай трехмерного сопоставления. Мне не пришло в голову заменить 3DM на PLSC, но, увидев доказательства, подход кажется вполне естественным.

Цуёси Ито