Как я понимаю, задача присваивания находится в P, поскольку венгерский алгоритм может решить ее за полиномиальное время - O (n 3 ). Я также понимаю, что задача присваивания - это целочисленная задача линейного программирования , но на странице Википедии говорится, что это NP-Hard. Для меня это означает, что проблема с назначением находится в NP-Hard.
Но, конечно, проблема назначения не может быть как в P, так и в NP-Hard, иначе P будет равно NP? Означает ли страница Wikipedia, что общий алгоритм решения всех проблем ILP - это NP-Hard? Несколько других источников утверждают, что ILP является NP-Hard, так что это действительно сбивает с толку мое понимание классов сложности в целом.
Ответы:
Если проблема NP-Hard, это означает, что существует класс экземпляров этой проблемы, NP-Hard. Вполне возможно, что другие конкретные классы экземпляров могут быть разрешимы за полиномиальное время.
Рассмотрим, например, проблему нахождения 3-окраски графа . Это хорошо известная проблема NP-Hard. Теперь представьте, что его экземпляры ограничены графами, например деревьями. Ясно, что вы можете легко найти 3-цветную окраску дерева за полиномиальное время (действительно, вы также можете найти 2-цветную окраску).
Рассмотрим решение проблемы на секунду. Метод доказательства твердости решаемой задачи заключается в разработке полиномиальной (карповой) редукции из другой задачи Q , известной как NP-Hard. В этом сокращении вы показываете, что существует функция f, которая отображает каждый экземпляр q проблемы Q на экземпляр проблемы P так , что: q является экземпляром yes дляP Q f q Q P Q представляет собой экземпляр да по P . Это подразумевает, что решение f ( q ) должно быть «как минимум так же сложно», как решение qQ⟺е( д) п е( д) Q само .
Обратите внимание , как это не требуется для образа равного множества экземпляров P . Поэтому это вполне возможно для проблемы Pе п п ограниченная некоторым подмножеством примеров, не будет сложной.
Чтобы вернуться к исходному вопросу:
источник
Нет, особые случаи могут быть проще.
Рассмотрим этот IP, например, при заданномaя≥ 0 для i ∈ [ 1 .. n ] :
улицаΣя = 1NИкся≥ 1 Икся∈ N i ∈ [ 1 .. n ] .
иxi∈Nдляi∈[1 ..n]
Это находит минимум средиa1, ... ,N (т , для которого, неизбежно, Икся= 1 в оптимальном решении). Нахождение минимума из N чисел является явно полиномиальной проблемой.
источник
Вы можете смоделировать полиномиально разрешимую проблему как IP. Это не значит, что проблема NP-трудна. Это просто означает, что не существует известного полиномиального алгоритма для решения IP-модели вашей задачи (если только P = NP).
Итак, как вы и предполагали, проблема назначения находится в P, но ваша IP-модель является NP-сложной.
источник
Нет, существует специальный вид целочисленной программы, если матрица ограничений TUM (полностью унимодулярная матрица), то она может быть преобразована в линейную программу, которая может быть решена за полиномиальное время.
источник
Проблема назначения - это не ILP, а проблема LP и, следовательно, не NP-hard.
источник