0

我被告知要确定一个图是否有哈密顿路径，它不会在多项式时间内计算。假设我们可以在多项式时间内解决它，我该如何证明呢？这是不可能的，因为它是NP难题？

4

1 回答 1

0

哈密​​顿路径问题是NP 完全的。
没有人证明不可能在多项式时间内解决它，但这种解决方案不太可能存在。如果你碰巧找到了一个，这意味着你已经证明了 P=NP，克莱数学研究所将奖励你一百万美元：）

于 2013-11-28T02:23:02.163 回答