P问题/NP问题/NP-Hard问题/NP-Complete问题

DuncanZhou

发布于 2020-01-21 10:33:21

1.2K0

发布于 2020-01-21 10:33:21

近日,论文中涉及到NP-Hard问题,写下笔记对以上问题进行区分.

P问题:在多项式时间内可以求解的问题. NP问题:在多项时间内不能求解,在多项式时间内可以验证的问题. NP-Hard问题:所有的NP问题在多项式时间内可以归约到该问题,该问题为NP-Hard问题. NP-Complete问题:一个问题即是NP-Hard问题,同时又是NP问题.

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度