Какие самые «сложные» проблемы используют за полиномиальное время?

Question

Недавно я прочитал семинарскую работу , в которой говорится:

Алгоритм сопоставления [для общих графиков] может быть расширен к взвешенному случаю, который представляется быть одним из самых "тяжелых" комбинаторных проблемы оптимизации, которые могут быть решается за полиномиальное время.

Сразу же возник следующий вопрос:

Знаете ли вы другие проблемы P-hard?

Пока я хотел бы определить P-hard как: «Полиномиальный алгоритм был найден очень поздно (после 1950 г.) в литературе по этой проблеме». (Или как лучше определить «hard «есть ли уже детерминированные алгоритмы, которые решают проблему за полиномиальное время?)

Answer 1

Простые числа в P .

Answer 2

На самом деле существуют «P-полные» задачи, что означает, что любая другая задача, которая может быть вычислена за полиномиальное время, может быть сведена к ним. Смотри http://en.wikipedia.org/wiki/P-complete.

Answer 3

Другая «сложная» P-задача - это решение «линейного программирования»:

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Answer 4

Если вы хотите немного изменить правила, то алгоритмы псевдополиномиального времени являются «самыми сложными», которые вы можете решить за «полиномиальное время».

Классический примерпсевдополиномиальный алгоритм является O(nW) решением динамического программирования для задачи о ранце .

Answer 5

Задача присваивания , которая может быть решена в O (n ³ ) с помощью модифицированного Венгерского алгоритма .