Все ли проблемы целочисленного линейного программирования NP-Hard?

11

Как я понимаю, задача присваивания находится в P, поскольку венгерский алгоритм может решить ее за полиномиальное время - O (n 3 ). Я также понимаю, что задача присваивания - это целочисленная задача линейного программирования , но на странице Википедии говорится, что это NP-Hard. Для меня это означает, что проблема с назначением находится в NP-Hard.

Но, конечно, проблема назначения не может быть как в P, так и в NP-Hard, иначе P будет равно NP? Означает ли страница Wikipedia, что общий алгоритм решения всех проблем ILP - это NP-Hard? Несколько других источников утверждают, что ILP является NP-Hard, так что это действительно сбивает с толку мое понимание классов сложности в целом.

Matt
источник
4
NP-hard означает, что (если P = NP) каждый многоплановый детерминированный алгоритм не выполняется в некотором (бесконечном) наборе экземпляров. Также обычно есть наборы простых примеров.
Сашо Николов
1
Обратите внимание, что утверждение не «каждый IP - NP-сложный», но «решение каждого IP - NP-сложный».
Рафаэль
1
Как примечание, IP для фиксированного измерения находится в P.
A.Schulz

Ответы:

20

Если проблема NP-Hard, это означает, что существует класс экземпляров этой проблемы, NP-Hard. Вполне возможно, что другие конкретные классы экземпляров могут быть разрешимы за полиномиальное время.

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

Рассмотрим решение проблемы на секунду. Метод доказательства твердости решаемой задачи заключается в разработке полиномиальной (карповой) редукции из другой задачи Q , известной как NP-Hard. В этом сокращении вы показываете, что существует функция f, которая отображает каждый экземпляр q проблемы Q на экземпляр проблемы P так , что: q является экземпляром yes дляпQеQQпQ представляет собой экземпляр да по P . Это подразумевает, что решение f ( q ) должно быть «как минимум так же сложно», как решение qQе(Q)пе(Q)Q само .

Обратите внимание , как это не требуется для образа равного множества экземпляров P . Поэтому это вполне возможно для проблемы Pепп ограниченная некоторым подмножеством примеров, не будет сложной.

Чтобы вернуться к исходному вопросу:

  • Задача о назначении может быть решена за полиномиальное время, т. Е. Решение каждого случая задачи о назначении может быть вычислено за полиномиальное время.
  • ILP - это NP-Hard: в общем, может быть трудно вычислить решение проблемы ILP, то есть существуют сложные примеры ILP.
  • Некоторые конкретные случаи ILP могут быть решены за полиномиальное время.
Стивен
источник
Не могли бы вы объяснить, необходимо ли отображать каждый экземпляр Q, не можем ли мы отобразить подмножество Q ? то есть должен ли предварительный образ f быть всем Q ? fQQfQ
Мат
Это не является необходимым для , чтобы отобразить каждый экземпляр Q до тех пор , как он сопоставляет (бесконечный) класс жестких экземпляров Q . Например, чтобы показать, что P является NP-Hard, можно привести сокращение от задачи 3-окраски, ограниченной плоскими графами. еQQп
Стивен
14

Нет, особые случаи могут быть проще.

Рассмотрим этот IP, например, при заданном aя0 для я[1 ..N] :

минΣязнак равно1NИксяaя

улица Σязнак равно1NИкся1
иxiNдляi[1 ..n] ИксяNя[1 ..N] .

Это находит минимум среди a1,...,aN (т , для которого, неизбежно, Иксязнак равно1 в оптимальном решении). Нахождение минимума из N чисел является явно полиномиальной проблемой.

Рафаэль
источник
0

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

Итак, как вы и предполагали, проблема назначения находится в P, но ваша IP-модель является NP-сложной.

Остен
источник
3
IP в ответе Рафаэля может быть решен за полиномиальное время. Другими словами, в целом мы не знаем о быстром алгоритме для решения IP, но есть особые случаи проблем с IP, для которых у нас есть быстрые алгоритмы.
Юхо
0

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

Цзяньхао Ма
источник
-4

Проблема назначения - это не ILP, а проблема LP и, следовательно, не NP-hard.

Юлия
источник
4
Я не уверен, почему вы думаете, что проблема назначения не является ILP. Случается, что в этом случае оптимальное решение для линейной программы также является оптимальным решением для целочисленной линейной программы ... но это не значит, что это не экземпляр ILP.
DW
Кроме того, отдельные экземпляры сами по себе никогда не являются NP-сложными. Вы хотите сказать «это на самом деле простой пример», но это гораздо более сложное утверждение (определите «легкий»).
Рафаэль