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

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

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

Учитывая , ориентированный граф и две метрики веса и по краям, определить, на пути , ( ). Учитывая два узла и , проблема состоит в том, чтобы найти путь от до st $G=(V,A)$ $w_1$ $w_2$ $P$ $w_i(P)=\sum_{a\in P}w_i(a)$ $i=1,2$ $s$ $t$ $P$ $s$ $t$ , где заданы положительные числа (пример: ограничение задержки и стоимость в сети). $w_i(P)\leq W_i$ $W_i$

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

Тогда они представляют ту же проблему, за исключением того, что метрики мультипликативны, т. . Чтобы доказать, что мультипликативная версия является -полной, они обеспечивают «полиномиальную» редукцию из аддитивной версии, просто положив и . $w'_i(P)=\prod_{a\in P}w'_i(a)$ $\mathsf{NP}$ $w'_i(a)=e^{w_i(a)}$ $W'_i=e^{W_i}$

Я очень озадачен этим сокращением. Так как и являются частью ввода (я думаю, в двоичном виде), то и не полиномиальны в и , Таким образом, сокращение не является полиномиальным. $W'_i$ $w'_i(a)$ $|w'_i(a)|$ $|W'_i|$ $|w_i(a)|$ $|W_i|$

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

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

np-hardness reductions Ламин
источник

Я проверил бумаги, это, безусловно, недостаток в их доказательстве.

Домоторп

Статья цитируется более 2000 раз. Это страшно ...

Ламин

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

Домоторп

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

Ответы: