问求解NP-hard问题的大O复杂度
EN

Stack Overflow用户

提问于 2020-11-30 16:25:31

回答 1查看 367关注 0票数 0

我有一个NP-hard优化问题，我将其形式化为混合整数线性规划(MILP)，并且正在使用Gurobi解决(对于小输入)。

我理解NP-hard意味着没有多项式时间算法来解决这个问题，除非是P=NP。对于使用Big O符号解决问题(例如，使用Gurobi)，我可以给出更精确的时间复杂度限制吗？有没有办法近似不同输入大小对复杂度的影响？

发布于 2020-12-01 01:08:29

混合整数编程的领域太多样化了，不能根据变量或约束的数量来定义复杂性规则。您需要查看有关您的特定问题或应用程序的文献-对于许多具体问题，都有可用的复杂性结果。这仍然不一定会影响到特定求解器的性能，或者您是否可以实际解决特定的问题实例。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/65070135

复制

相似问题

问求解NP-hard问题的大O复杂度EN