推 ZaneLin: 根據定義 NP-Complete是NP且為NP-hard 12/29 23:29
→ ZaneLin: NP-Complete是NP問題 可以在多項式時間驗證，但目前還找 12/29 23:31
→ ZaneLin: 不到多項式時間解決它 12/29 23:31
推 Aa841018: 如果p!=np，代表np的問題無法於多項式時間內解決，而NPC 12/29 23:32
→ Aa841018: 是np中最難的問題，所以也無法在polynomial time解決 12/29 23:32
→ eefat: 這面寫np可以在非決定性的演算法中 12/30 09:33
→ eefat: *解決* 12/30 09:33
→ eefat: 就算是非決定性演算法也可以算解決問題吧？ 12/30 09:33
推 Aa841018: *非決定是否可在polynomial time內解決 12/30 09:38
推 ok8752665: 可以阿 前提是真的有這種演算法 現今的演算法記得是不 12/30 10:02
→ ok8752665: 存在非決定式的 12/30 10:02
推 mistel: 存在啊，只是電子計算機上行不通，要在其他計算模型上， 12/30 10:51
→ mistel: 如量子電腦上BQP問題可以用猜測式的方法去解，質因數分解 12/30 10:51
→ mistel: 問題這種，只是受限於量子計算還很不成熟，所以目前為止 12/30 10:51
→ mistel: 計算出的結果可能有錯誤（這部分我就不熟了 12/30 10:51
→ mistel: 話說我記得中央考過寫非決定式算法？ 第一次看到應該都蠻 12/30 10:52
→ mistel: 吐血的 12/30 10:52
→ ok8752665: 好吧 對量子電腦相關的完全沒概念 12/30 11:52