[理工] 演算法 np eefat PTT批踢踢實業坊

作者: eefat (ffff) 2019-12-29 23:10:11

https://i.imgur.com/B7R3in2.jpg
請問一下np-complete是不是np問題？
我畫底線那句直覺來說np-complete是np裡面最難解的問題
但是下面又寫np-complete沒辦法在多項式時間內解決
不太懂他們的關係
謝謝

作者: ZaneLin (不發廢文呦) 2019-12-29 23:29:00

根據定義 NP-Complete是NP且為NP-hardNP-Complete是NP問題可以在多項式時間驗證，但目前還找不到多項式時間解決它

作者: Aa841018 (andrew) 2019-12-29 23:32:00

如果p!=np，代表np的問題無法於多項式時間內解決，而NPC是np中最難的問題，所以也無法在polynomial time解決

作者: eefat (ffff) 2019-12-30 09:32:00

https://i.imgur.com/myKkRqh.jpg這面寫np可以在非決定性的演算法中*解決*就算是非決定性演算法也可以算解決問題吧？

作者: Aa841018 (andrew) 2019-12-30 09:38:00

*非決定是否可在polynomial time內解決

作者: ok8752665 (dd8752665) 2019-12-30 10:02:00

可以阿前提是真的有這種演算法現今的演算法記得是不存在非決定式的

作者: mistel (Mistel) 2019-12-30 10:51:00

存在啊，只是電子計算機上行不通，要在其他計算模型上，如量子電腦上BQP問題可以用猜測式的方法去解，質因數分解問題這種，只是受限於量子計算還很不成熟，所以目前為止計算出的結果可能有錯誤（這部分我就不熟了話說我記得中央考過寫非決定式算法？第一次看到應該都蠻吐血的

作者: ok8752665 (dd8752665) 2019-12-30 11:52:00

好吧對量子電腦相關的完全沒概念

繼續閱讀