找到一些有趣的定义:

找到一些有趣的定义:

我想我们可以更简洁地回答。我回答了一个相关的问题，并从那里复制了我的答案

但首先，np难问题是指我们无法证明存在多项式时间解的问题。某些“问题- p”的np -硬度通常是通过在多项式时间内将已经证明的np -难问题转换为“问题- p”来证明的。

要回答剩下的问题，首先需要了解哪些np困难问题也是np完全问题。如果一个NP难问题属于集合NP，则它是NP完全问题。要属于集合NP，一个问题需要 (i)决策问题， (ii)问题的解的数量应该是有限的，每个解应该是多项式长度，并且 (iii)给定一个多项式长度的解，我们应该能够说出问题的答案是或否 现在，很容易看出，可能有许多NP困难问题不属于集合NP，更难解决。作为一个直观的例子，旅行推销员的优化版本(我们需要找到一个实际的时间表)比旅行推销员的决策版本(我们只需要确定长度<= k的时间表是否存在)更难。

这是对问题的非正式回答。

3233可以写成另外两个大于1的数的乘积吗?有没有办法绕过Königsberg的七座桥而不经过任何一座桥两次?这些问题都有一个共同的特点。如何有效地确定答案可能并不明显，但如果答案是“是”，那么就有一个简短而快速的证明。在第一种情况下，61的非平凡因式分解(53是另一个质因数);第二种是通过桥梁的路线(符合约束条件)。

决策问题是一组答案为“是”或“否”的问题，这些问题只在一个参数上有所不同。假设问题COMPOSITE={"Is n Is COMPOSITE ": n是一个整数}或EULERPATH={"图G有欧拉路径吗?": G是有限图}。

现在，有些决策问题即使没有明显的算法，也可以用在高效的算法上。250多年前，欧拉发现了一种有效的算法来解决“Königsberg的七座桥”这样的问题。

另一方面，对于许多决策问题，如何得到答案并不明显，但如果你知道一些额外的信息，如何证明你得到了正确的答案就很明显了。COMPOSITE是这样的:试除法是显而易见的算法，它很慢:要分解一个10位数的数，你必须尝试10万个可能的除数。但是，例如，有人告诉你61是3233的除法，简单的长除法是一种有效的方法来证明他们是正确的。

复杂性类NP是一类决策问题，其中“是”的答案有简短的陈述，快速检查证明。像复合。重要的一点是，这个定义并没有说明问题有多难。如果你有一个正确有效的方法来解决一个决策问题，只要写下解决方案中的步骤就足够了。

算法的研究仍在继续，新的聪明的算法一直在被创造出来。一个你今天可能不知道如何有效解决的问题，明天可能会有一个有效的解决方案(如果不是明显的)。事实上，直到2002年，研究人员才找到了一个有效的COMPOSITE解决方案!有了这些进步，人们真的想知道:这一点关于简短的证明只是一种幻觉吗?也许每个适合有效证明的决策问题都有有效的解决方案?没有人知道。

也许这个领域最大的贡献来自于发现一类特殊的NP问题。通过摆弄电路模型进行计算，斯蒂芬·库克发现了一个NP类型的决策问题，可以证明，这个问题比任何其他NP问题都难，甚至更难。布尔可满足性问题的有效解决方案可以用于创建NP中任何其他问题的有效解决方案。不久之后，理查德·卡普(Richard Karp)证明了其他一些决策问题也可以达到同样的目的。这些问题在某种意义上是NP中“最难”的问题，被称为NP完全问题。

当然，NP只是一类决策问题。许多问题不是自然地以这种方式表述的:“找到N的因子”，“找到图G中访问每个顶点的最短路径”，“给出一组变量赋值，使以下布尔表达式为真”。尽管人们可能非正式地将一些这样的问题称为“NP问题”，但从技术上讲，这并没有多大意义——它们不是决策问题。其中一些问题甚至可能具有与NP完全问题相同的力量:对这些(非决策)问题的有效解决方案将直接导致对任何NP问题的有效解决方案。像这样的问题被称为np困难。

对于这个特别的问题有很好的答案，所以没有必要写我自己的解释。所以我会试着提供关于不同类型计算复杂度的优秀资源。

对于那些认为计算复杂度只是关于P和NP的人来说，这里有关于不同计算复杂度问题的最详尽的资源。除了OP提出的问题，它还列出了大约500种不同类型的计算问题，并给出了很好的描述，还列出了描述这类问题的基础研究论文。

我假设您正在寻找直观的定义，因为技术定义需要相当长的时间来理解。首先，让我们记住一个基本概念来理解这些定义。

决策问题:回答是或不是的问题。

---

现在，让我们定义这些复杂性类。

P

P是一个复杂度类，表示所有决策问题的集合，可以在多项式时间内解决。

也就是说，给定一个问题的实例，答案是或否可以在多项式时间内决定。

例子

给定一个连通图G，它的顶点可以用两种颜色来着色，从而没有边是单色的吗?

算法:从一个任意顶点开始，将其涂成红色，将其所有邻居涂成蓝色，然后继续。当你用尽顶点时停止，或者你被迫让一条边的两端都是相同的颜色。

---

NP

NP是一个复杂度类，它表示所有决策问题的集合，其中答案是“是”的实例具有可以在多项式时间内验证的证明。

这意味着如果有人给我们一个问题的实例和一个证明(有时称为证人)，答案是肯定的，我们可以在多项式时间内检查它是否正确。

例子

整数因式分解是NP。这是一个给定整数n和m的问题，是否存在一个1 < f < m的整数f，使得f能整除n (f是n的一个小因子)?

这是一个决策问题，因为答案是是或不是。如果有人给我们一个问题的实例(他们给了我们整数n和m)和一个1 < f < m的整数f，并声称f是n的因数(证书)，我们可以通过执行n / f的除法在多项式时间内检查答案。

---

非完全多项式

NP- complete是一个复杂度类，它表示NP中所有问题X的集合，其中可以在多项式时间内将任何其他NP问题Y减少到X。

直观地说，这意味着如果我们知道如何快速解决X，我们就可以快速解决Y。准确地说，Y可约为X，如果有一个多项式时间算法f在多项式时间内将Y的实例Y转换为X = f(Y)的实例X，其性质是Y的答案是yes，当且仅当f(Y)的答案是yes。

例子

3-SAT。在这个问题中，我们得到了一个3子句析取(or)的连词(and)，这种形式的语句

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

其中，每个x_vij是一个布尔变量或有限预定义列表(x_1, x_2，…)中的一个变量的负数。x_n)。

可以看出，每一个NP问题都可以简化为3-SAT。这个证明是技术性的，需要使用NP的技术定义(基于非确定性图灵机)。这就是众所周知的库克定理。

NP完全问题之所以重要，是因为如果可以找到一个确定的多项式时间算法来解决其中一个问题，那么每个NP问题都可以在多项式时间内解决(一个问题可以统治所有问题)。

---

NP-hard

直观地说，这些问题至少和np完全问题一样难。注意，NP难问题不一定是NP问题，也不一定是决策问题。

这里的精确定义是，如果存在一个np完全问题Y，那么问题X是np难的，这样Y可以在多项式时间内约化为X。

但由于任何np完全问题都可以在多项式时间内化简为任何其他np完全问题，所以所有np完全问题都可以在多项式时间内化简为任何np难问题。那么，如果在多项式时间内存在一个NP难问题的解，那么在多项式时间内就存在所有NP问题的解。

例子

停止问题是np难问题。这个问题是给定一个程序P和输入I，它会停止吗?这是一个决策问题，但不属于NP范畴。很明显，任何np完全问题都可以简化为这个问题。另一个例子是，任何np完全问题都是np难的。

我最喜欢的np完全问题是扫雷问题。

---

P = NP

这是计算机科学中最著名的问题，也是数学科学中最重要的杰出问题之一。事实上，克莱研究所为解决这个问题提供了100万美元(斯蒂芬·库克在克莱网站上的文章相当不错)。

很明显P是NP的子集。悬而未决的问题是NP问题是否有确定的多项式时间解。人们普遍认为，事实并非如此。这里有一篇关于P = NP问题的最新(和重要性)的杰出文章:P vs NP问题的现状。

这方面最好的书是加里和约翰逊合著的《计算机与顽固性》。