简单理解 NP, P, NP-complete和NP-Hard

2024-11-17 11:25:02 203人阅读

P是一类可以通过确定性图灵机（以下简称图灵机）在多项式时间(Polynomial time)内解决的问题集合。

NP是一类可以通过非确定性图灵机( Non-deterministic Turing Machine)在多项式时间(Polynomial time)内解决的决策问题集合。

P是NP的子集，也就是说任何可以被图灵机在多项式时间内解决的问题都可以被非确定性的图灵机解决。

接下来说说NP 里最难得问题 NP-complete。

其定义如下，

如果一个决策问题 L 是 NP-complete的，那么L具备以下两个性质：

1) L 是 NP（给定一个解决NP-complete的方案(solution，感兴趣的读者可以思考一下solution 和 answer的区别)，可以很快验证是否可行，但不存在已知高效的方案。）

2) NP里的任何问题可以在多项式时间内转为 L。

而NP-Hard只需要具备NP-complete的第二个性质，因此NP-complete是NP-Hard的子集。

这四者的关系如下图（假设P!=NP）：

简单理解 NP, P, NP-complete和NP-Hard

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们