Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в сокращении, и случаи задачи, к которой вы сводите, были полиномиально ограничены по размеру задачи.
Затем я увидел, что Википедия дала те же самые общие инструкции для такого рода доказательств, но я не был в этом уверен, пока не увидел, что Гэри и Джонсон в основном говорят то же самое. В частности, они говорят: «Если NP-труден в сильном смысле и существует псевдополиномиальное преобразование из в , то NP-труден в сильном смысле», и «Обратите внимание, что по определению алгоритм полиномиального времени также является алгоритмом псевдополиномиального времени».
Конечно, я принимаю слово Гэри и Джонсона об этом - я просто не понимаю, как это может быть правильно, и в этом я бы хотел помочь. Вот мои (предположительно ошибочные) рассуждения…
Существуют сильно NP-полные задачи, и все они (по определению) сильно NP-сложные, а также NP-полные. Каждая NP-полная задача может (по определению) быть сведена к любой другой за полиномиальное (и, следовательно, псевдополиномиальное) время. Учитывая утверждения Garey & Johnson, мне кажется, что каждая NP-полная проблема сильно NP-полная, и, следовательно, что каждая NP-трудная проблема сильно NP-сложная. Это, конечно, делает концепцию сильной NP-твердости бессмысленной ... так чего мне не хватает?
Редактировать / обновить (основываясь на ответе Цуёси Ито):
Требование (d) из определения (псевдо) полиномиального преобразования (псевдо) полиномиального преобразования Гэри и Джонсона состоит в том, чтобы наибольшая численная величина в результирующем случае была полиномиально ограниченной, как функция размера задачи и максимальной числовой величины оригинала. Это, конечно, означает, что если исходная задача является NP-трудной в сильном смысле (то есть, даже когда ее числовые величины полиномиально ограничены по размеру задачи), это также будет справедливо для проблемы, к которой вы сводитесь. Это не обязательно будет иметь место для обычного сокращения многопоточности (то есть, без этого дополнительного требования).
источник
Ответы:
Согласно терминологии, изложенной в статье Гэри и Джонсона, преобразования за полиномиальное время не обязательно являются псевдополиномиальными преобразованиями, поскольку они могут нарушать пункт (d) в определении 4.
источник
Чтобы расширить ответ Цуёси:
В контексте Гэри и Джонсона рассмотрим переход от РАЗДЕЛА (стр. 47, раздел 3.1) к МНОГОПРОЦЕССОРНОМУ ПЛАНИРОВАНИЮ (стр. 65, раздел 3.2.1, пункт (7)).
Преобразование (по ограничению) включает в себя установкуD = 12Σa ∈ Aл ( а ) л ( а ) Q2 ∀ я∈ DΠ [ ф( Я) ] ≤ q2 [ Я] , [ Я] ) (т.е. пункт (d) в определении псевдополиномиального преобразования).
Возможно, вы захотите прочитать Википедию по соответствующей теме . Например, у нас есть алгоритм полиномиального времени на основе динамического программирования для NP-полной задачи KNAPSACK - по крайней мере, до тех пор, пока числа достаточно малы. Когда числа становятся слишком большими, этот алгоритм «полиномиального времени» будет отображать «экспоненциальное поведение». (G & J, стр. 91, раздел 4.2)
источник