NP-Completeness,2,NP-Completeness,- Computability - Analysis of Algorithms - NP-Completeness,3,Analysis of Algorithm,For many problems, there may be several competitive algorithms. Which one should I use?,Analysis of algorithms. framework for comparing algorithms and prediction performance. case study: sorting,Computational complexity. framework for studying intrinsic difficulty of problems.,4,图灵机,1936年图灵提出了一个抽象计算模型 图灵机，并用它来精确定义可计算函数。图灵机的基本思想是模拟人用纸笔进行数学运算的过程，这个运算过程可分解为下面两种简单的动作： 1.在纸上写或擦除某个符号； 2.把注意力从纸的一个位置移动到另一个位置。 在每个阶段将由执行运算的人决定下一步的动作，而他的决定依赖于此人当前所关注的是纸上哪个位置的符号，以及此人当前思维的状态。,5,Turing Machine,6,Deterministic Turing Machine,定义 一台图灵机由一个八元组所组成 TM = ( Q, T, I, , b, q0, qaccept , qreject ) 其中 Q：一个有限状态集； T：一个有限符号集（字母表）； I：输入字符集，I T； b：空符，bTI； ：QT 的子集Q(TL, R, S)，即转移函数或有限状态控制函数，其中L, R表示读写头左移或右移，S表示读写头原地不动； q0：表示初始状态； qaccepr：表示终止（接受）状态； qreject：表示拒绝状态。 这里规定是单值映射，所以也称为确定型图灵机。,7,一个例子,例：设TM =(0,1,10,11,0,1,“ ”(空格), 0,1, 0)，做一个以1的个数表示数值的整数加法运算,在磁带上的数据设为0000001110110000，就是3+2的意思。转移函数定义如下： 0,0 0,0R 0,1 1,1R 1,0 10,1R 1,1 1,1R 10,0 11,0L 10,1 10,1R 11,0 E 11,1 0,0S 在 xx,y aa,bb 中，xx是当前状态，y是当前格子的值，aa是程序下一步的状态，b是当前格的修改值。例如第一行指令 0,0 0,0R，意思就是如果机器读到格子的值是0，就将其仍变成0，状态变为0，读写头向右移动一格。最后两行中的E代表错误，S代表停机。,8,图灵机的格局序列（粗体的字符表示读写头的当前位置）,9,其他类型的图灵机,双向无限带图灵机。其带子向左向右都是无限长的，与确定型图灵机基本模型不同的是，它的带子没有左端、带头永远不会走出两端。 多带多头图灵机。它具有一个有穷控制器，k个带头和k条带子，每条带子都是双向无穷的，并且各带头在操作时相互独立，除改写带符、左右移动外，还可以保持不动。 非确定型图灵机。这种类型的图灵机具有一个有限控制器和一条单向无限带，对于一个给定的状态，机器的下一动作可以有穷多个选择，每个选择包括一个新状态，一个要打印的带符号和一个带头移动方向。,10,非确定型图灵机,定义: 一个非确定型图灵机（NDTM）由下述八元组给出： NDTM = (Q，T，I，b，q0，qaccept，qreject) 其中Q, T, I, b, q0 和qr 的定义与确定型图灵机的相同，唯一的区别在于状态控制函数（转移函数）。 非确定型图灵机的状态控制函数 给出的下一个动作不是唯一确定的,即为多值映射,它的值域是一个有穷集合A。因此非确定型图灵机在下一时刻的动作可以有多种选择。在处理问题时，对于(q1, al, , ak)的多个值，非确定型图灵机对于其中任意一个值都存在一个格局序列可以推导下去，只要其中有一种可以到达终止状态qaccept ，就说该问题是可以处理的（输入字符串被接受或函数是可计算的）。,11,Overview of showing problems to be NP-complete,在证明一个问题为NP完全问题时，要依赖于三个关键概念： - 判定问题与最优化问题 - 归约 - 第一个完全问题,12,Decision problems vs. optimization problems,Many problems of interest are optimization problems, in which each feasible (i.e., “legal“) solution has an associated value, and we wish to find the feasible solution with the best value. For example, in a problem that we call SHORTEST-PATH, we are given an undirected graph G and vertices u and v, and we wish to find the path from u to v that uses the fewest edges. (In other words, SHORTEST-PATH is the single-pair shortest-path problem in an unweighted, undirected graph.),13,Decision problems vs. optimization problems,NP-completeness applies directly not to optimization problems, however, but to decision problems, in which the answer is simply “yes“ or “no“ (or, more formally, “1“ or “0“). The relationship between an optimization problem and its related decision problem works in our favor when we try to show that the optimization problem is “hard.“ That is because the decision problem is in a sense “easier,“ or at least “no harder.“,14,Decision problems vs. optimization problems,Although showing that a problem is NP-complete confines us to the realm of decision problems. there is a convenient relationship between optimization problems and decision problems. We usually can cast a given optimization problem as a related decision problem by imposing a bound on the value to be optimized. .,optimization problems,decision problems,imposing a bound on the optimization value,15,Decision problems vs. optimization problems,In other words, if an optimization problem is easy, its related decision problem is easy as well. Stated in a way that has more relevance to NP-completeness, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard.,16,Reductions,The above notion of showing that one problem is no harder or no easier than another applies even when both problems are decision problems. We take advantage of this idea in almost every NP-completeness proof, as follows. Let us consider a decision problem, say A, which we would like to solve in polynomial time. We call the input to a particular problem an instance of that problem;,17,Reductions,for example, in PATH, an instance would be a particular graph G, particular vertices u and v of G, and a particular integer k. Now suppose that there is a different decision problem, say B, that we already know how to solve in polynomial time. Finally, suppose that we have a procedure that transforms any instance of A into some instance of B with the following characteristics:,1）The transformation takes polynomial time. 2）The answers are the same. That is, the answer for is “yes“ if and only if the answer for is also “yes.“,18,Reductions,We call such a procedure a polynomial-time reduction algorithm and, it provides us a way to solve problem A in polynomial time: 1）Given an instance of problem A, use a polynomial-time reduction algorithm to transform it to an instance of problem B. 2