什么是使用多项式时间的“硬”的问题？

Question

最近我读到研讨会工作其说：

  

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

立即以下问题来到我的脑海：

你知道其他的 “P-难” 的问题？

现在我想定义P-坚硬如：“多项式算法在文献中对于发现问题非常晚（1950年以后）” 的（或者一个人如何能更好地确定“。硬”，如果已经有一个确定性算法解决了在多项式时间的问题？）

Answer 1

实际上有“P-完整”的问题，这意味着，可以在多项式时间来计算每个其它问题可减小到它们。请参阅 http://en.wikipedia.org/wiki/P-complete 。

Answer 2

素数是P中。

Answer 3

另一个 “硬” P问题求解 “线性规划”：

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

Answer 4

如果您想通融了一下，然后伪多项式时间算法是“重”，可以在“多项式时间”解决。

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

Answer 5

其可以在O解决（N ^{3 SUP>）由改性}匈牙利算法。