Что “самые трудные” проблемы используют полиномиальное время?
Недавно я считал работу семинара, которая говорит:
Алгоритм соответствия [для общих графиков] может быть расширен на взвешенный случай, который, кажется, одна из "самых трудных" комбинаторных проблем оптимизации, которые могут быть решены в полиномиальное время.
Сразу следующий вопрос прибыл по моему мнению:
Вы знаете другие проблемы "P-hard"?
На данный момент я хотел бы определить P-hard как: "Полиномиальный алгоритм был найден очень поздним (после 1950) в литературе для той проблемы". (Или как один лучше мог определить "трудно", если уже существует детерминированные алгоритмы, который решает проблему в полиномиальное время?)
5 ответов
На самом деле существуют «P-полные» задачи, что означает, что любая другая задача, которую можно вычислить за полиномиальное время, может быть сведена к ним. См. http://en.wikipedia.org/wiki/P-complete .
Задача присваивания , которая может быть решена за O (n 3 ) с помощью модифицированного венгерского алгоритма .
Другая «сложная» проблема P - это решение «линейного программирования»:
Если вы хотите немного изменить правила, тогда алгоритмы псевдополиномиального времени являются «самыми сложными», которые вы можете решить за «полиномиальное время».
Классическим примером псевдополиномиального алгоритма является решение O (nW) динамического программирования задачи о ранце .