Можно ли действительно продемонстрировать сильную NP-твердость, используя простые сокращения по времени?

17

Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в сокращении, и случаи задачи, к которой вы сводите, были полиномиально ограничены по размеру задачи.

Затем я увидел, что Википедия дала те же самые общие инструкции для такого рода доказательств, но я не был в этом уверен, пока не увидел, что Гэри и Джонсон в основном говорят то же самое. В частности, они говорят: «Если NP-труден в сильном смысле и существует псевдополиномиальное преобразование из в , то NP-труден в сильном смысле», и «Обратите внимание, что по определению алгоритм полиномиального времени также является алгоритмом псевдополиномиального времени».ΠΠΠΠ

Конечно, я принимаю слово Гэри и Джонсона об этом - я просто не понимаю, как это может быть правильно, и в этом я бы хотел помочь. Вот мои (предположительно ошибочные) рассуждения…

Существуют сильно NP-полные задачи, и все они (по определению) сильно NP-сложные, а также NP-полные. Каждая NP-полная задача может (по определению) быть сведена к любой другой за полиномиальное (и, следовательно, псевдополиномиальное) время. Учитывая утверждения Garey & Johnson, мне кажется, что каждая NP-полная проблема сильно NP-полная, и, следовательно, что каждая NP-трудная проблема сильно NP-сложная. Это, конечно, делает концепцию сильной NP-твердости бессмысленной ... так чего мне не хватает?

Редактировать / обновить (основываясь на ответе Цуёси Ито):

Требование (d) из определения (псевдо) полиномиального преобразования (псевдо) полиномиального преобразования Гэри и Джонсона состоит в том, чтобы наибольшая численная величина в результирующем случае была полиномиально ограниченной, как функция размера задачи и максимальной числовой величины оригинала. Это, конечно, означает, что если исходная задача является NP-трудной в сильном смысле (то есть, даже когда ее числовые величины полиномиально ограничены по размеру задачи), это также будет справедливо для проблемы, к которой вы сводитесь. Это не обязательно будет иметь место для обычного сокращения многопоточности (то есть, без этого дополнительного требования).

Магнус Ли Хетланд
источник
Большой! Мой математический ТА сделал это вчера, и я думал, что это подозрительно. Теперь я могу дать ему ссылку.
Рафаэль

Ответы:

14

Согласно терминологии, изложенной в статье Гэри и Джонсона, преобразования за полиномиальное время не обязательно являются псевдополиномиальными преобразованиями, поскольку они могут нарушать пункт (d) в определении 4.

Цуёси Ито
источник
1
Правильно - поэтому полиномиальный алгоритм обязательно является псевдополиномиальным, но сокращение полинома не обязательно то, что G & J называет псевдополиномиальным преобразованием. На самом деле, их пункт (d) - это именно то, чего я считал отсутствующим (то есть, какое-то ограничение на размер числа). Благодарю.
Магнус Ли Хетланд
9

Чтобы расширить ответ Цуёси:

В контексте Гэри и Джонсона рассмотрим переход от РАЗДЕЛА (стр. 47, раздел 3.1) к МНОГОПРОЦЕССОРНОМУ ПЛАНИРОВАНИЮ (стр. 65, раздел 3.2.1, пункт (7)).

Преобразование (по ограничению) включает в себя установку Dзнак равно12ΣaAL(a)L(a)Q2яDΠ[е(я)]Q2[я],[я]) (т.е. пункт (d) в определении псевдополиномиального преобразования).

L(a)L(a)|A|

Возможно, вы захотите прочитать Википедию по соответствующей теме . Например, у нас есть алгоритм полиномиального времени на основе динамического программирования для NP-полной задачи KNAPSACK - по крайней мере, до тех пор, пока числа достаточно малы. Когда числа становятся слишком большими, этот алгоритм «полиномиального времени» будет отображать «экспоненциальное поведение». (G & J, стр. 91, раздел 4.2)

Даниэль Апон
источник