据我理解,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问题: NP问题是指可以在非确定性多项式时间内解决的问题。 非确定性算法分为两个阶段。 非确定性猜测阶段和非确定性验证阶段。 NP问题类型 NP完全问题 NP难问题 NP完全问题: 1.如果一个决策问题A具有以下两个特性,则称其为NP完全问题: 它属于NP类。 NP中的每个其他问题都可以在多项式时间内转换为P。 一些例子: 背包问题 子集和问题 顶点覆盖问题
NP完全问题是一组问题,对于其中的任何一个问题,任何其他NP问题都可以在多项式时间内归约,并且其解决方案仍然可以在多项式时间内验证。也就是说,任何NP问题都可以转化为NP完全问题中的任何一个。 - 非正式地讲,NP完全问题是至少与NP中的任何其他问题一样“棘手”的NP问题。