[理工] 算法 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

好吧对量子电脑相关的完全没概念

继续阅读