在计算机科学中，什么是NP完全问题？

据我理解，P集合是能够在确定性图灵机上用多项式时间解决的问题集合。而NP集合则需要用非确定性图灵机以多项式时间来解决。这意味着我们可以并行地检查所有不同变量的组合，每个实例都需要花费多项式时间。如果问题是可解的，那么至少有一个这些并行图灵机实例将停止于“是”的状态。这也意味着，如果您对变量/解决方案做出了正确的猜测，那么您只需要在多项式时间内检查其有效性即可。
NP-Hard问题比NP问题更难，甚至使用图灵机的非确定性也无法在多项式时间内求解。因此，并行计算无法帮助解决这些问题。
NP-Complete则是NP和NP-Hard的交集。根据我的理解： 1.NP-Complete中的问题至少与NP集合中最难的问题一样难。 2.所有NP-Complete问题的类别是等效的，即NP-Complete集合中的任何问题都可以被降解为其他NP-Complete问题。这意味着，如果任何一个NP-Complete问题有高效的解决方案，那么所有NP-Complete问题都可以使用同样的解决方案来解决。
如果NP-Complete集合中的任何问题可以在确定性图灵机上以多项式时间解决，则整个NP-Complete集合也可以以确定性多项式时间解决。而且由于NP-Complete问题至少与NP集合中最难的问题一样难，所有在NP集合中的问题（这些问题与NP-Complete集合中的问题相等或更容易）都将受到确定性多项式运行时间的限制，从而扩展了P集合超过了NP集合，导致P = NP。
如果我翻译有误，请告诉我。

上面NP完全问题的定义是正确的，但我认为我可以对它们的哲学重要性进行一些赞美，因为没有人解决这个问题。
你会遇到的几乎所有复杂问题都是NP完全问题。这个类别有一些非常基本的东西，与易于解决的问题在计算上似乎有所不同。它们有自己的特点，很容易就能认出来。这基本上意味着任何中等复杂的算法对你来说都是无法精确解决的--调度、优化、打包、覆盖等。
但如果你遇到的问题是NP完全问题，也并非一切都失去了希望。有一个广阔而非常技术化的领域，人们研究近似算法，这将给你提供接近NP完全问题解决方案的保证。其中一些保证非常强--例如，对于3sat问题，你可以通过一个非常明显的算法获得7/8的保证。更好的是，在现实中，有一些非常强的启发式算法，擅长为这些问题提供很好的答案（但没有保证！）。
请注意，两个非常著名的问题--图同构和分解--还不知道是P还是NP。

NP问题：

1. NP问题是指可以在非确定性多项式时间内解决的问题。
2. 非确定性算法分为两个阶段。
3. 非确定性猜测阶段和非确定性验证阶段。

NP问题类型

1. NP完全问题
2. NP难问题

NP完全问题：

1.如果一个决策问题A具有以下两个特性，则称其为NP完全问题：

1. 它属于NP类。
2. NP中的每个其他问题都可以在多项式时间内转换为P。

一些例子：

• 背包问题
• 子集和问题
• 顶点覆盖问题

NP完全问题是一组问题，对于其中的任何一个问题，任何其他NP问题都可以在多项式时间内归约，并且其解决方案仍然可以在多项式时间内验证。也就是说，任何NP问题都可以转化为NP完全问题中的任何一个。 - 非正式地讲，NP完全问题是至少与NP中的任何其他问题一样“棘手”的NP问题。