1、首先涉及的基本概念如下。

(1)确定性算法(Determinism )把a作为问题的一种求解算法，在算法的整个执行过程中，每个步骤都能得到确定性解的算法就是确定性算法。

)2)非确定性算法(Nondeterminism ) :将a作为求解问题的算法，它将问题分解为猜测阶段和验证阶段两部分，其中

推测阶段：在此阶段，将为问题输入实例生成任意字符串y，并且字符串y的值可能随算法的执行而不同，因此推测以非确定的形式运行。 验证阶段(在此阶段，使用确定性算法)在有限时间内进行验证)检查推测阶段生成的串y是否为适当的形式，否则停止算法得到否； 如果串y是合适的形式，验证它是否是问题的解，否则停止算法得到是，否则停止算法得到否。 就是验证推测出的解的正确性。 此外，有以下概念：

对于多项式时间(Polynomial )规模为n的输入，最坏情况下的执行时间为o(n^k )。 其中，如果k是某个常数，则在计算算法为多项式时间的算法复杂度的理论中，算法的计算时间，即时间复杂度m ) n )小于或等于算法规模n的多项式倍数。 也就是说，m ) n )是n的多项式函数，例如，时间复杂度为o(n^2)是多项式时间，时间复杂度为o )2^n )不是n的多项式函数，因此不是多项式时间。 2、p类问题、NP类问题、NP难问题、NPC问题

(1) p类问题)多项式时间可以解决的问题。 )2) NP类问题(Nondeterminism Polynomial ) :多项式时间上“可验证”的问题。 也就是说，不是判定这个问题是否有解，而是在多项式时间内推测该解是否正确。 也就是说，这个问题的推测过程是不确定的，但某个解的验证可以在多项式时间内完成。 p类问题是NP问题，但不知道是否是NP问题的真正子集。 )3) NPC类问题) nondeterminismpolynomialcomplete )有了这样的NP问题，所有的NP问题都可以与之近似。 也就是说，解决了这个问题，所有的NP问题都可以解决。 其定义应满足两个条件：

首先，它必须是NP问题； 而且，所有的NP问题都可以概括为它。 要证明npc问题的想法：

证明它至少是一个NP问题，然后证明一个已知的NPC问题可以与其近似。 (4) NP-hard问题) NP-hard问题是满足NPC问题定义的第二条，但不一定需要满足第一条的问题(也就是说，NP-hard问题是

NPC问题的范围很广，NP-Hard问题不限于NP )，即所有NP问题都可以与之近似，但他不一定是NP问题。 NP-Hard问题也很难找到多项式的算法，但它不一定是NP问题，因此不在我们的研究范围之内。 即使在NPC问题上发现了多项式级算法，NP-Hard问题也可能得不到多项式级算法。 事实上，由于NP-Hard放宽了限制条件，它比所有NPC问题在时间上更复杂，可能难以解决。 这四个问题的关系可以用下图表示。

在3、2中提到的另一个概念是规约/合同化

简而言之，可以理解为问题a可以与问题b约定化，问题b的解必须是问题a的解。 “问题a可以归结为问题b”也可以理解为问题b的答案可以用于解决问题a。 因此，解决a也不难解决b。 由此也可知，问题b的时间复杂度一定在问题a以上。 《算法导论》中列举了这样的例子。 例如，目前存在求解一元一次方程和求解一元二次方程两个问题。 那么，前者可以规定为后者。 也就是说，只要知道求解一元二次方程的方法，就一定能够求解一元一次方程。 你可以写两个程序分别对应两个问题。 于是，就能找到一个“规则”。 根据这个规则改变求解一元一次方程的程序的输入数据，用于求解一元二次方程的程序中，两个程序总是得到相同的结果。 该规则即两个方程的对应项系数不变，一元二次方程的二次项系数为0。 规约的定义表明，一个问题被规约为另一个问题，增加了时间的复杂性，也增加了问题的适用范围。 通过对某个问题重复规约，可以继续寻找应用范围更广的算法，而不是复杂度更高、复杂度低但只能用于小种类问题的算法。 存在这样的NP问题，所有的NP问题都可以与之近似。 也就是说，解决了这个问题，所有的NP问题都可以解决。 这种问题的存在令人难以置信，更奇怪的是，这样的问题不仅有一个，还有很多，那是一种问题。 这类问题是传说中的NPC问题，也就是NP-完全问题。