1
我知道我們可以將FPTAS應用於像0-1揹包這樣的弱NP問題。爲什麼我們不能擁有FPTAS的強NP完整問題
但是爲什麼我們不能將相同的主體應用於像bin裝箱這樣的強NP問題。我還查看了關於相同但很少理解的wiki頁面。
A
回答
2
如果一個強烈的NP完全問題有FPTAS，你可以「欺騙」近似算法來給出最優解。細節在這裏：http://www.idi.ntnu.no/~mlh/algkon/complexity.pdf
這個FPTAS的存在將給出一個NP-完全問題的多項式時間算法。
相關問題
- 1. 什麼是NP問題？
- 2. 我們如何知道NP完全問題是NP中最難的？
- 3. 第一個NP完全問題如何顯示爲NP完全？
- 4. NP完整嗎？
- 5. 所有的NP問題都是NP完成的嗎？
- 6. 證明NP完全問題
- 7. NP和P的問題需要什麼？
- 8. 集成np，np完整，np很難或者以上都不是？
- 9. 有關獨立集問題的NP-完備性的問題
- 10. 什麼是NP-中級問題？
- 11. NP完整的定義
- 12. 爲什麼我不能在libgdx上播放完整的歌曲
- 13. 爲什麼我的程序不能讀取完整文件？
- 14. 爲什麼我不能做一個完整的外連接
- 15. IDL爲什麼不完整？
- 16. 爲什麼當我擁有#id #id時CSS不能工作？
- 17. SVN：強制他們完整
- 18. 爲什麼我們有clojure memoize功能？
- 19. NP和co-NP有什麼區別
- 20. 爲什麼我的結構有一個不完整的定義？
- 21. 我的功能有什麼問題？
- 22. 我的功能有什麼問題？
- 23. 我的功能有什麼問題？
- 24. 我的功能有什麼問題？ C＃
- 25. 我的功能有什麼問題？
- 26. NP中的所有問題都不是P NP-complete？
- 27. 如果siftDown比siftUp更好，爲什麼我們擁有它？
- 28. 爲什麼我們仍然在struct sockaddr_un中擁有sun_family？
- 29. 爲什麼我們不能在C＃
- 30. 爲什麼我們不能循環'...'？
這個問題屬於http://programmers.stackexchange.com/ – tripleee
這個問題似乎是離題，因爲它是關於理論計算機科學，這是更適合在cs.stackexchange.com。 – templatetypedef
@ tripleee-爲什麼這屬於程序員？這是一個CS理論問題。 – templatetypedef