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