NP难问题和NP完全问题的区别

NP问题：

NP问题是一组难以找到但易于验证的问题，由非确定性机器在多项式时间内解决。

NP难问题：

如果存在 NP-Complete 问题 Y，则问题 X 是 NP-Hard，使得 Y 在多项式时间内可简化为 X。NP-Hard 问题与 NP-Complete 问题一样难。NP-Hard 问题不必属于 NP 类。

NP完全问题：

如果存在 NP 问题 Y，则问题 X 是 NP 完全的，使得 Y 在多项式时间内可简化为 X。NP 完全问题与 NP 问题一样难。如果一个问题是 NP 和 NP-Hard 问题的一部分，那么它就是 NP-Complete。非确定性图灵机可以在多项式时间内解决 NP-Complete 问题。

NP-Hard 和 NP完全问题的区别：

NP-hard	NP完全问题
当且仅当存在可以在多项式时间内简化为 X 的 NP 完全问题(例如 Y)时，才能解决 NP-Hard 问题(例如 X)。	NP-Complete 问题可以通过非确定性算法/图灵机在多项式时间内解决。
要解决这个问题，它不必在 NP 中。	要解决这个问题，必须同时是 NP 和 NP-hard 问题。
不必是一个决策问题。	NP完全问题完全是一个决策问题。
示例：停止问题、顶点覆盖问题等。	示例：确定图是否具有哈密顿圈、确定布尔公式是否可满足、电路可满足性问题等。