2、法1。现设一台每小时能作M次运算的计算机，并设求解某一问题已有了两个不同的算法。算法A对规模为n的实例约需作n2次运算而算法B则约需作2n次运算。于是，运用算法A在一小时内可解一个规模为的实例，而算法B则只能解一个规模为log2M的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作100万次运算，则算法A一小时大约可解一个规模为n=60000的实例，而算法B在一小时内只能解一个规模的实例且n每增加1，算法B求解时所化的时间就将增加1倍。例如算法B求解一个n=50的实例将连续运算357年多。现设计算速度提高了100倍，这对计算机来讲已是一个相
3、当大的改进。此时算法A可解问题的规模增大了10倍，而算法B可解问题的规模只增加了log2100<7。前者可解问题的规模成倍成倍地增加而后者则几乎没有什么改变，今天无法求解的问题将来也很少有希望解决。由于这一原因，人们对算法作了如下的分类：（多项式算法）设A是求解某一问题D的一个算法，对D的一个规模为n的实例，用fA(D,n)表示用算法A求解这一实例所作的初等运算的次数。若存在一个多项式P(n)和一个正整数N，当n≥N时总有fA(D,n)≤P(n)（不论求解D的怎样的实例，只要其规模为n），则称算法A为求解问题D的一个多项式时间算法，简称多项式算法。（指数算
4、法）设B是求解某一问题D的一个算法，fB(D,n)为用算法B求解D的一个规模为n的实例时所用的初等运算次数，若存在一个常数k>0，对任意正整数N，总可找到一个大于N的正整数n及D的一个规模为n的实例，对这一实例有fB(D,n)=O(2^kn)，则称B为求解问题D的一个指数算法。多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。下面的表1列出了在规模大约为n时各类算法的计算量，而表2则反映了当计算机速度提高10倍、100倍时，各类算法在1小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，
5、后两个是指数时间的）表1几个多项式和指数时间复杂性函数增长情况算法要求的计算量规模n的近似值101001000n101001000nlogn336649966n31031061092n10241.27×10301.05×10301n!3628800101584×102567表21小时内可解的问题实例的规模算法要求的计算量用现在计算机用快10倍计算机用快100倍计算机nN110N1100N1nlognN28.2N267N2n3N32.15N34.64N32nN4N4+3.32N4+6.64n!N5≤N5+2≤N5+3由上可知4n2与2n2都是O(n2)，nl
6、ogn+3n是O(nlogn)，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。下面介绍六个最初的NP难问题（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一个实例。命题逻辑中合取范式(CNF)的可满足性问题(SAT)是当代理论计算机科学的核心问题,是一典型的NP完全问题.考虑CNF：A=C1∧⋯∧Ci∧⋯∧Cn(1)子句Ci具有如下形式：Pi,1∨Pi,2∨⋯∨Pi,ki∨┐Pr
7、i,1∨┐Pri,2∨⋯∨┐Pri,kri,其中Pi,1,Pi,2,⋯,Pi,ki,┐Pri,1,┐Pri,2,⋯,┐Pri,kri是两两不同的文字,Pi,j为命题变元集{P1,P2,⋯,Pm}中的一个变元,文字┐Pi表示变元Pi的非,m表示命题变元的个数,n表示子句的个.一个SAT问题是指:对于给定的CNF是否存在一组关于命题变元的真值指派使得A为真.下面介绍六个最初的NP难问题（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一个实例。下面介绍六个最初的NP难问题如果A为真,则CN
8、F的每个子句中必有一个命题变元为1(真),将每个子句中的每个命题变
