Срок действия возведения в степень при полиномиальном сокращении времени

15

Я задал этот вопрос 10 дней назад на cs.stackexchange здесь, но у меня не было никакого ответа.

В очень известной статье (в сетевом сообществе) Wang & Crowcroft представили некоторые результаты полноты вычисления пути при нескольких аддитивных / мультипликативных ограничениях. Первая проблема заключается в следующем:Nп

Учитывая , ориентированный граф и две метрики веса W 1 и W 2 по краям, определить, на пути Р , ш I ( P ) = Σ Р ш я ( ) ( я = 1 , 2 ). Учитывая два узла s и t , проблема состоит в том, чтобы найти путь P от s до t st wграммзнак равно(В,A)вес1вес2пвеся(п)знак равноΣaпвеся(a)язнак равно1,2sTпsT , где W i заданы положительные числа (пример: ограничение задержки и стоимость в сети).веся(п)WяWя

Авторы доказывают, что эта проблема является -полной, предоставляя полиномиальную редукцию из PARTITION.Nп

Тогда они представляют ту же проблему, за исключением того, что метрики мультипликативны, т. . Чтобы доказать, что мультипликативная версия является N P -полной, они обеспечивают «полиномиальную» редукцию из аддитивной версии, просто положив w i ( a ) = e w i ( a ) и W i = e W i .веся'(п)знак равноΠaпвеся'(a)Nпвеся'(a)знак равноевеся(a)Wя'знак равноеWя

Я очень озадачен этим сокращением. Так как и w i ( a ) являются частью ввода (я думаю, в двоичном виде), то | w i ( a ) | и | W i | не полиномиальны в | w i ( a ) | и | W я | , Таким образом, сокращение не является полиномиальным.Wiwi(a)|wi(a)||Wi||wi(a)||Wi|

Я что-то упустил тривиально или в доказательстве есть недостаток? Я сомневаюсь в достоверности доказательства, даже если результат явно верен.

Ссылка на документ: Чжэн Ван, Джон Кроукрофт. Маршрутизация качества обслуживания для поддержки мультимедийных приложений . Журнал IEEE по отдельным областям в сообщениях 14 (7): 1228-1234 (1996).

Ламин
источник
1
Я проверил бумаги, это, безусловно, недостаток в их доказательстве.
Домоторп
Статья цитируется более 2000 раз. Это страшно ...
Ламин
Ну, вероятно, большинство цитат не используют этот конкретный результат, а также, в конце концов, это все еще верно. Мне рассказывали примеры, когда им приходилось снимать несколько бумаг, основываясь на ложном результате. Кроме того, эта уловка возведения в степень является настолько стандартной, что, вероятно, большинство людей даже не продумывает и не осознает, что вы сделали, что длина входных данных изменяется.
Домоторп

Ответы:

9

Доказательство, представленное в статье, не является окончательным.

Однако сам заявленный результат верен. Его можно легко получить, слегка изменив сокращение и используя SUBSET PRODUCT вместо SUBSET SUM.

Полезная ссылка для решения проблемы SUBSET PRODUCT:
/cs/7907/is-the-subset-product-problem-np-complete

Гамов
источник