Сумма подмножества против продукта подмножества (сильная или слабая твердость NP)

15

Я надеялся, что кто-нибудь сможет объяснить мне, почему именно проблема подмножеств является сильно NP-трудной, в то время как проблема сумм подмножеств является NP-трудной.

Подмножество Сумма: Дано и Т , существует ли подмножество X ' такое , что Σ я Х ' х я = Т .X={x1,...,xn}TXiXxi=T

Подгруппа товаров: Дано и Т , существует ли подмножество X ' такое , что Π я Х ' х я = Т .X={x1,...,xn}TXiXxi=T

Я всегда думал, что эти две проблемы были эквивалентны - экземпляр SS можно преобразовать в экземпляр SP с помощью возведения в степень, а экземпляр SP в SS - с помощью логарифмов. Это привело меня к выводу, что они оба принадлежали к одному и тому же классу NP-харда - то есть оба они были слабо NP-хард.

Кроме того, похоже, что одно и то же повторение может быть использовано для решения обеих проблем с использованием динамического программирования с очень небольшим изменением (замена вычитания в SS на деление в SP).

Так было до тех пор, пока я не прочитал главу 8 «Теории вычислений» Бернарда Морета (для тех, у кого нет книги, у нее есть доказательство твердости продукта с подмножеством через X3C - сильно NP-трудная проблема).

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


ОБНОВЛЕНИЕ : Оказывается, что подмножество является лишь слабо NP-полным (целевой продукт экспоненциально в ). Гари и Джонсон опубликовали это в своей колонке NP-завершенности в 1981 году , но я думаю, что это было менее заметно, чем их раннее утверждение в их книге.Ω(n)

РДН
источник
5
Вероятно, было бы хорошо представить, как бы вы реализовали свой алгоритм динамического программирования. Тогда вы найдете, что было не так.
Ёсио Окамото
@ MohammadAl-Turkistany: Это в последнем разделе этой колонки
RDN

Ответы:

5

Относительно проблемы эквивалентности суммы подмножества и продукта подмножества В отношении продукта подмножества есть технические особенности. Произведение x's = T на самом деле является псевдополиномиальным, если T не экспоненциально! Таким образом, доказательства того, что Subset Product является NP Hard, не являются (по техническим причинам !!!) совершенно правильными!

Однако, если дать обещание, что T большое, то уменьшение с помощью логарифмов до подмножества суммы дает НЕСТАНДАРТНУЮ СУММУ ПОДЗЕТА, превышающую действительные значения! Это означает, что алгоритм Psuedopolynomial для суммы подмножеств не применяется! Хотя логарифмы малы, десятичные разряды мешают псевдополиномиальному динамическому программированию!

надеюсь, это поможет

Зила

Зелах 02
источник
2
Оказывается, вы все время были правы относительно того, что сокращения были неправильными (то есть, утверждая, что они показывают сильную NP-полноту, когда они этого не делают). Благодарность!
RDN
8

Во-первых, использование возведения в степень для перехода от SS к SP работает (с использованием базы 2, а не базы ), но увеличивает размер участвующих чисел. Слабая NP-твердость означает, что если числа малы (или, точнее, обозначены как одинарные), проблема больше не является сложной. Следовательно, использование возведения в степень создает экземпляры SP с экспоненциальным размером даже для простых экземпляров SS, где числа записываются в унарном виде.e

Во-вторых, использование логарифмов для перехода от SP к SS не работает, поскольку логарифмы обычно генерируют нецелые значения. SS и SP определяются с использованием целых чисел, а логарифмы часто приводят к трансцендентным значениям, которые трудно представить или вычислить.

<edit>

Пусть целое число, A > 0 , тогда log 2 A рационально тогда и только тогда, когда A является степенью 2, и трансцендентным в противном случае. Во-первых, если log 2 A = pAA>0log2AA для ненулевых целых чиселpиq, тогдаA=2 plog2A=pqpq ,Aq=2с. Поэтому мы имеем, чтоA=2rпосредством простого разложения. Кроме того,Arq=2p, поэтому дляAможно выбратьq=1иp=r,чтобы доказать, чтоlog2Aрационально.A=2pqAq=2pA=2rArq=2pAq=1p=rlog2A

Нам просто нужно показать, что никогда не бывает трансцендентным. Это вытекает из теоремы Гельфонда-Шнайдера , для эквивалентной формулировки (как можно найти на вики-странице) «если α и γ ненулевые алгебраические числа и мы берем любой ненулевой логарифм α , то ( log γ ) / ( log α ) = log α γ является либо рациональным, либо трансцендентным. " Это также легко проверить, взяв обратное утверждение теоремы и задав α β = γ и, следовательно, βlog2Aαγα(logγ)/(logα)=logαγαβ=γ .β=logαγ

</edit>

Наконец, рассмотрим, что происходит, когда мы пробуем алгоритм динамического программирования из SS на SP. Поскольку мы используем продукты, а не суммы, их число резко возрастает, и математика произвольной точности внезапно становится фактором времени выполнения. Вот почему алгоритм не может быстро решить экземпляры SP, даже если числа в унарном виде.

Алекс тен Бринк
источник
это приводит к несколько интересному частному случаю. для какого класса чисел журнал может быть выражен как рациональное и не требующее бесконечной точности? в этом случае проблемы действительно были бы почти эквивалентны и сводимы друг к другу. это также, кажется, ведет к «естественному» алгоритму приближения.
vzn
1
ISSO(nlogx)ISPO(nx)
RDN
1
@vzn, RDN: Я отредактировал характеристику, когда логарифм трансцендентен. Что касается увеличения в сокращении, это зависит от вашего определения «законного»: сокращение является правильным , но его эффективность не является полиномиальной, и, следовательно, ничего не говорит о NP-твердости. Следовательно, это не правильное сокращение по времени , но это правильное сокращение (без квалификаторов).
Алекс тен Бринк
cninicc=2c
1

Буквальное объяснение состоит в том, что проблема Subset Product является NP-полной из-за сокращения от сильно NP-полной задачи, такой как точное покрытие 3-множествами. При таком «сильном» сокращении входные целые числа ограничены некоторой полиномиальной функцией от числа целых чисел в результирующем примере задачи Подмножество продуктов.

P=NP

Мухаммед Аль-Туркистани
источник
Да, я понимаю это. Мой вопрос был о том, почему заключение, которое я сделал ранее, было неверным (то есть, эквивалентность SS и SP).
RDN
@rdn В этом смысле нет эквивалента, если P = NP.
Мухаммед Аль-Туркистани
Да, я понял. Но я хочу знать, что случилось с моими сокращениями в любом направлении.
RDN
Можете ли вы наметить ваши сокращения?
Мухаммед Аль-Туркистани
I(SS)=X,SI(SP)=Y,PI(SS)I(SP)P=eSYi=eXiSP=eSI(SP)I(SS)S=log(P)Xi=log(Yi)PS=log(P)