algorithm - 使用多项式时间的“最难”问题是什么？

Question

最近我读了一篇研讨会的作品，上面写着：

匹配算法[用于一般图]可以扩展到加权情况，这似乎是可以在多项式时间内解决的“最难”的组合优化问题之一。

我立刻想到了以下问题：

你知道其他“P-hard”问题吗？

现在我想将 P-hard 定义为：“在该问题的文献中很晚才（1950 年之后）发现了多项式算法”。（或者如果已经有一种确定性算法可以在多项式时间内解决问题，那么如何更好地定义“困难”？）

score 10 · Accepted Answer

10

于 2010-02-13T20:43:37.937 回答

score 6 · Accepted Answer

实际上存在“P-完全”问题，这意味着可以在多项式时间内计算的所有其他问题都可以简化为它们。请参阅http://en.wikipedia.org/wiki/P-complete。

score 5 · Accepted Answer

另一个“难”的 P 问题是解决“线性规划”：

score 3 · Accepted Answer

如果您想稍微改变规则，那么伪多项式时间算法是您可以在“多项式时间”中解决的“最难”的算法。

伪多项式算法的一个典型例子是背包问题O(nW)的动态规划解。

score 2 · Accepted Answer

2

可以通过修改后的匈牙利算法在 O(n ^{3 ) 内解决}的分配问题。

于 2010-02-13T23:12:40.373 回答

5 回答 5