Каковы "самые трудные" проблемы с использованием полиномиального времени?

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

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

Сразу же на мой взгляд пришел следующий вопрос:

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

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

Ответы

Ответ 1

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

Ответ 4

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

Классическим примером псевдополиномиального алгоритма является O(nW) динамическое программирующее решение проблема ранца.