0
有人告诉我，要确定一个图是否有哈密尔顿路径，它不会在多项式时间内计算。让我们假设我们可以在多项式时间内解决它，我怎么能证明这一点？这是不可能的，因为这是NP难题？哈密顿路径分析
Q
哈密顿路径分析
A
回答
0
Hamiltonian Path Problem是NP-complete。
没有人有证明它是不可能在多项式时间内解决它，但这种解决方案是不太可能存在。如果你碰巧找到一个，这意味着你已经证明P = NP，而粘土数学研究院将从字面上为你奖励一百万美元:)
相关问题
- 1. 哈密顿路径在Haskell
- 2. 哈密顿路径算法
- 3. 哈密顿电路
- 4. 枚举*所有*哈密尔顿路径
- 5. 最短哈密尔顿路径和bitmasking
- 6. 哈密顿路径问题的变化
- 7. 在完全无向加权图中查找哈密尔顿路径与哈密尔顿电路
- 8. 如何将TSP转化为最小哈密尔顿路径？
- 9. 为什么TSP NP-hard而哈密尔顿路径NP-complete？
- 10. 唯一拓扑排序意味着存在哈密顿路径
- 11. 使用旅行推销员求解器来确定哈密顿路径
- 12. 为什么欧拉路径可以在线性时间内实现，而不是哈密尔顿路径？
- 13. 寻找哈密顿电路TSP问题的问题
- 14. 快速哈密顿周期计算
- 15. O（N）中的哈密顿循环
- 16. 的NullPointerException这个哈密顿圈问题
- 17. 分析路径数据
- 18. 分析Neo4j路径查询
- 19. 曼哈顿距离
- 20. 在给定开始点和结束点的图中找到哈密尔顿路径的数量
- 21. 绘制一个具有1800个哈密尔顿路径的7顶点简单图形
- 22. 路径解析
- 23. 解析路径
- 24. 加密加密路径
- 25. 曼哈顿距离澄清
- 26. 曼哈顿CodinGame中的IndexOutOfRangeException
- 27. 曼哈顿布局算法
- 28. 曼哈顿距离的Python
- 29. A *曼哈顿距离
- 30. 曼哈顿距离的Fortran