作者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/cn.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