什么是“最难”的？使用多项式时间的问题？
最近我读了一篇研讨会作品，其中写道：
[针对一般图]的匹配算法可以扩展 对于加权情况，这似乎是 成为“最难”的组合之一 优化问题可以 在多项式时间内求解。
我立即想到了以下问题：
你知道其他“P-hard”问题吗？
现在我想将 P-hard 定义为：“多项式算法很晚才被发现（1950 年后）在该问题的文献中”。（或者，如果已经存在一种可以在多项式时间内解决问题的确定性算法，那么如何更好地定义“硬”？）
Recently I read a seminar work which says:
The matching algorithm [for general graphs] can be extended
to the weighted case, which appears to
be one of the "hardest" combinatorial
optimization problems that can be
solved in polynomial time.
Immediately the following question came to my mind:
Do you know other "P-hard" problems?
For now I would like to define P-hard as: "A polynomial algorithm was found very late (after 1950) in the literature for that problem". (Or how could one better define "hard" if there is already a deterministic algorithms which solves the problem in polynomial time?)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
Primes 位于 P 中。
Primes is in P.
实际上存在“P-完全”问题，这意味着可以在多项式时间内计算的所有其他问题都可以简化为它们。请参阅http://en.wikipedia.org/wiki/P-complete。
There are actually "P-complete" problems, which means that every other problem that can be computed in polynomial time can be reduced to them. See http://en.wikipedia.org/wiki/P-complete.
另一个“硬”P 问题是解决“线性规划”：
http://en.wikipedia.org /wiki/Linear_programming#算法
Another "hard" P problem is solving "linear programming":
http://en.wikipedia.org/wiki/Linear_programming#Algorithms
如果你想稍微改变一下规则，那么伪多项式时间算法就是您可以在“多项式时间内”解决的“最难”问题。
伪多项式算法的一个经典示例是 背包问题。
If you want to bend the rules a bit, then pseudo-polynomial time algorithms are the "hardest" that you can solve in "polynomial time".
A classic example of a pseudo-polynomial algorithm is the
O(nW)dynamic programming solution to the knapsack problem.赋值问题，可以在 O(n3) 中解决通过修改后的匈牙利算法。
The Assignment Problem which can be solved in O(n3) by the modified Hungarian Algorithm.