algorithm - 什么是计算机科学中的 NP-complete？

Question

<分区>

Answer 1

什么是NP ？

NP 是所有 decision problems 的集合(带有是或否答案的问题)"is"答案可以在多项式时间内验证 (O(n^k) 其中 n 是问题大小，k 是常数)由 deterministic Turing machine .多项式时间有时被用作快速或快速的定义。

什么是P ？

P 是所有决策问题的集合，确定性图灵机可以在多项式时间内解决。由于它们可以在多项式时间内求解，因此它们也可以在多项式时间内得到验证。因此P是NP的子集。

什么是NP-Complete ？

NP 中的问题 x 也属于 NP-Complete 当且仅当 NP 中的所有其他问题都可以快速(即在多项式时间内)转换为 x。

换句话说:

1. x 在 NP 中，并且
2. NP 中的每个问题都是 reducible到x

所以，NP-Complete 如此有趣的原因在于，如果要快速解决任何一个 NP-Complete 问题，那么所有 NP 问题都可以解决很快。

另见帖子 What's "P=NP?", and why is it such a famous question?

什么是NP-Hard ？

NP-Hard 是至少与 NP 中最难的问题一样难的问题。请注意，NP-Complete 问题也是 NP-hard 问题。然而，尽管以 NP 作为前缀，但并非所有 NP-hard 问题都是 NP(甚至是决策问题)。也就是说 NP-hard 中的 NP 并不意味着非确定性多项式时间。是的，这令人困惑，但它的用法是根深蒂固的，不太可能改变。