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