Kar*_*ell 10 algorithm np-hard time-complexity
最近我读了一个研讨会的工作说:
匹配算法[对于一般图]可以扩展到加权情况,这似乎是可以在多项式时间内解决的"最难"的组合优化问题之一.
我立即想到了以下问题:
你知道其他"P-hard"问题吗？
现在我想把P-hard定义为:"在这个问题的文献中发现了一个多项式算法(1950年以后)".(或者,如果已经有一个确定性算法可以解决多项式时间内的问题,那怎么能更好地定义"硬"？)
小智 10
Primes在P中.
Ant*_*ima 6
实际上存在"P完全"问题,这意味着可以在多项式时间内计算的每个其他问题都可以减少到它们.见http://en.wikipedia.org/wiki/P-complete.
Guy*_*Guy 5
另一个"硬"P问题是解决"线性规划":
http://en.wikipedia.org/wiki/Linear_programming#Algorithms
归档时间：
15 年，6 月 前
查看次数：
2607 次
最近记录：
12 年，5 月 前