Является ли проблема «подмножество продукта» NP-полной?

Задача подмножества сумм является классической NP-полной задачей:

Учитывая список чисел и цель , есть ли подмножество чисел из которое суммирует к ? $L$ $k$ $L$ $k$

Студент спросил меня, является ли этот вариант проблемы, называемый проблемой «подмножество продукта», NP-полным:

Имея список чисел и цель , существует ли подмножество чисел из , произведение которых равно ? $L$ $k$ $L$ $k$

Я немного искал и не мог найти никаких ресурсов, которые говорили бы об этой проблеме, хотя, возможно, я пропустил их.

Является ли проблема подмножества продукта NP-полной?

complexity-theory np-complete reductions templatetypedef
источник

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

j_random_hacker

@j_random_hacker, да, если вы не можете найти ответ после поиска на этом сайте и в Интернете, я предлагаю вам опубликовать отдельный вопрос. Это хороший вопрос с хорошим ответом (подсказка: при взятии журналов у вас остается нечто, не являющееся целым числом; с другой стороны, подумайте, что дает возведение в степень с размером чисел), но это немного касательно и было бы лучше в своем собственном вопросе.

@DW: Спасибо, когда у меня будет время, я сделаю так, как ты предлагаешь!

j_random_hacker

Ответы:

В комментарии упоминается сокращение с X3C до ПОДВОДНОГО ПРОДУКТА, приписываемое Яо. Учитывая цель сокращения, было нетрудно догадаться, каким могло быть снижение.

Определения:

Точная крышка на 3 комплекта (X3C)

Дано конечное множество с кратное 3 и набор из 3-элементных подмножеств , содержит ли точное покрытие для , где и каждый элемент в встречается ровно один раз в ? $X$ $|X|$ $C$ $X$ $C$ $C'$ $X$ $C' \subseteq C$ $X$ $C'$

СУБСЕТНЫЙ ПРОДУКТ

Имея список чисел и цель , существует ли подмножество чисел из , произведение которых равно ? $L$ $k$ $L$ $k$

Чтобы уменьшить экземпляр X3C до экземпляра SUBSET PRODUCT:

Установить биективное отображение между членами и первым простые числа. Замените члены подмножеств и сопоставленными простыми числами. $X$ $|X|$ $X$ $C$
Для каждого подмножества в умножьте его члены вместе; результирующий список продуктов для экземпляра SUBSET PRODUCT. Поскольку простые числа используются для отображения на шаге 1, произведения гарантированно эквивалентны, если подмножества эквивалентны по теореме об уникальной факторизации . $C$ $L$
Умножьте члены вместе; В результате получается значение для экземпляра SUBSET PRODUCT. $X$ $k$

Простые множители точно члены . Простые множители чисел в точно соответствуют членам подмножеств. Поэтому любое решение нового экземпляра SUBSET продукта может быть превращено в раствор X3C путем сопоставления членов раствора обратно к подмножествам в . $k$ $X$ $L$ $C$ $L$ $C$

Каждый из 3 шагов преобразования включает в себя операции, полиномиальные по размеру ввода или размер члена . Первый простые числа могут быть сгенерированы во времени O ( ) с помощью сита Эратосфена и гарантированно помещаются в пространство по теореме простых чисел . $|X|$ $X$ $|X|$ $|X|$ $O(|X|^2 \ln |X|)$

Кайл Джонс
источник

+1, но для сокращения, я думаю, мы требуем, чтобы первое | X | простые числа могут быть представлены в виде числа битов, полиномиальных по | X | - Прав ли я в этом, и если да, есть ли у нас эта гарантия?

j_random_hacker

Отличный момент. Я добавил параграф для решения этой проблемы.

Кайл Джонс

Спасибо, эта теорема это цементирует! Не для мелочей, но в соответствии со страницей, на которую вы ссылаетесь, k-е простое число приблизительно равно k log k, и, учитывая, что сито Эратосфена, по-видимому, вычисляет все простые числа до n за время O (n log log n) , подставляя n = k log k, по-видимому, дает время O (k * log (k) * log (log (k log k))), а не O (k) (ваше O (| X |)), для вычисления первого k простой путь таким образом.

j_random_hacker

Кайл Джонс, разве не важно, что шаг 3 создаст число

экспоненциального размера? Это сокращение действительно полиномиального времени?

k

$k$

user1742364

k

$k$

k

$k$

| X |

$|X|$

O (n^{2})

$O(n^2)$

k

$k$

P

$P$

X

$X$

k

$k$

O (\log P)

$O(\log P)$

Согласно [ 1 ]: да, это

Я также цитирую ту же ссылку: Комментарии: между этим и проблемой 42 существует тонкое техническое различие: в первом случае используется псевдоэффективный алгоритм, полученный путем представления чисел в унарном виде; однако, если все NP-полные проблемы не могут быть решены с помощью быстрых алгоритмов, проблема подмножества продукта не может быть решена «эффективными» методами, использующими даже это необоснованное входное представление.

посмотрите на [2] для сокращения. [2]: Товарищи Майкл и Нил Коблиц. «Фиксированная сложность параметров и криптография». Прикладная алгебра, алгебраические алгоритмы и коды, исправляющие ошибки (1993): 121-131.

AJed
источник

Фактическое сокращение или цитирование в журнальной статье было бы хорошо, если это возможно.

templatetypedef

@templatetypedef В Garey и Johnson приведено точное покрытие на 3 комплекта. Из-за личного общения с Яо.

AJed

Сокращение в криптографическом документе связано с другой проблемой, в которой целевой продукт заменяется конгруэнцией с целевым числом по модулю, указанному в данном примере. (Хотя, если я правильно понимаю доказательства, они все равно получают слабую твердость, потому что модуль имеет экспоненциальную величину.)

Джеффри Босбум