[理工] 演算法 np

看板Grad-ProbAsk作者 (ffff)時間6年前 (2019/12/29 23:10), 編輯推噓5(5推 0噓 14→)
留言19則, 5人參與, 6年前最新討論串1/1
https://i.imgur.com/B7R3in2.jpg
請問一下np-complete是不是np問題？ 我畫底線那句直覺來說np-complete是np裡面最難解的問題 但是下面又寫np-complete沒辦法在多項式時間內解決 不太懂他們的關係 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.76.185.73 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577632213.A.C97.html
推
12/29 23:29, 6年前 , 1F
根據定義 NP-Complete是NP且為NP-hard
12/29 23:29, 1F
→
12/29 23:31, 6年前 , 2F
NP-Complete是NP問題 可以在多項式時間驗證，但目前還找
12/29 23:31, 2F
→
12/29 23:31, 6年前 , 3F
不到多項式時間解決它
12/29 23:31, 3F
推
12/29 23:32, 6年前 , 4F
如果p!=np，代表np的問題無法於多項式時間內解決，而NPC
12/29 23:32, 4F
→
12/29 23:32, 6年前 , 5F
是np中最難的問題，所以也無法在polynomial time解決
12/29 23:32, 5F
→
12/30 09:32, 6年前 , 6F
12/30 09:32, 6F
→
12/30 09:33, 6年前 , 7F
這面寫np可以在非決定性的演算法中
12/30 09:33, 7F
→
12/30 09:33, 6年前 , 8F
*解決*
12/30 09:33, 8F
→
12/30 09:33, 6年前 , 9F
就算是非決定性演算法也可以算解決問題吧？
12/30 09:33, 9F
推
12/30 09:38, 6年前 , 10F
*非決定是否可在polynomial time內解決
12/30 09:38, 10F
推
12/30 10:02, 6年前 , 11F
可以阿 前提是真的有這種演算法 現今的演算法記得是不
12/30 10:02, 11F
→
12/30 10:02, 6年前 , 12F
存在非決定式的
12/30 10:02, 12F
推
12/30 10:51, 6年前 , 13F
存在啊，只是電子計算機上行不通，要在其他計算模型上，
12/30 10:51, 13F
→
12/30 10:51, 6年前 , 14F
如量子電腦上BQP問題可以用猜測式的方法去解，質因數分解
12/30 10:51, 14F
→
12/30 10:51, 6年前 , 15F
問題這種，只是受限於量子計算還很不成熟，所以目前為止
12/30 10:51, 15F
→
12/30 10:51, 6年前 , 16F
計算出的結果可能有錯誤（這部分我就不熟了
12/30 10:51, 16F
→
12/30 10:52, 6年前 , 17F
話說我記得中央考過寫非決定式算法？ 第一次看到應該都蠻
12/30 10:52, 17F
→
12/30 10:52, 6年前 , 18F
吐血的
12/30 10:52, 18F
→
12/30 11:52, 6年前 , 19F
好吧 對量子電腦相關的完全沒概念
12/30 11:52, 19F
‣ 更多 eefat 的文章
文章代碼(AID): #1U2C7LoN (Grad-ProbAsk)