算法理论的研究对象：两类抽象问题 R 优化问题（也称为极值问题） Φ一个优化问题通常可以用以下四个部分来描述 实例集合：若干实例组成集合D,其中每一个实例含有一 个问题所有输入的数据信息 可行解集：每一个实例有一个解集合S(),其中的每一个解 都满足问题的条件，称为可行解 目标函数：映射c(σ)：S()→R 最优化：求最优解·ot()∈S(),使得对任意一个可行解 o∈S(),都有c(oopt()≥c(o)或者c(oopt()≤c(o) Φ一个优化问题也可以视为一个判定问题
算法理论的研究对象：两类抽象问题 优化问题（也称为极值问题） 一个优化问题通常可以用以下四个部分来描述 ⚫ 实例集合：若干实例I组成集合D，其中每一个实例I含有一 个问题所有输入的数据信息 ⚫ 可行解集：每一个实例I有一个解集合S(I)，其中的每一个解 都满足问题的条件，称为可行解 ⚫ 目标函数：映射c(σ): S(I)→ℜ ⚫ 最优化：求最优解 σopt (I) ∈S(I)，使得对任意一个可行解 σ∈S(I)，都有c(σopt (I)) ≥c(σ) 或者c(σopt (I)) ≤c(σ) 一个优化问题也可以视为一个判定问题
算法理论的研究对象：两类抽象问题 R 判定问题（也称为识别问题） 仅有两种可能的答案：“是”或者“否” Φ可以将一个判定问题视为一个函数 它将问题的输入集合映射到问题解的集合{01} 以路径判断问题为例： ●给定一个图G=(V,E)和顶点集V中的两个顶点u,V ,判断G中是否存在一条路u和V之间的路 如果用i=<G,u,V>表示该问题的一个输入 则：函数PATH()=1(当u和V之间存在一条路时) -则：函数PATH()=0(当u和V之间不存在一条路时)
算法理论的研究对象：两类抽象问题 判定问题（也称为识别问题） 仅有两种可能的答案：“是”或者“否” 可以将一个判定问题视为一个函数 ⚫ 它将问题的输入集合I映射到问题解的集合{0 1} 以路径判断问题为例： ⚫ 给定一个图G=(V, E) 和顶点集V中的两个顶点u, v ⚫ 判断 G 中是否存在一条路u和v之间的路 ⚫ 如果用 i=<G, u, v>表示该问题的一个输入 ━ 则：函数PATH(i)=1 （当u和v之间存在一条路时） ━ 则：函数PATH(i)=0 （当u和v之间不存在一条路时）
P和NP R P和NP都是问题的集合 ΦP是所有可在多项式时间内用确定算法求解的判定问题的集合 ·对于一个问题X,若存在一个算法XSolver,能在Onk)时间 内求解(k为某个常数)，那么就称这个问题属于P ΦNP是所有可用多项式时间算法验证其猜测准确性的问题的集合 ·对于一个问题X,若存在一个算法XChecker,能在多项式 时间复杂度内给出验证结果，那么就称这个问题属于NP Φ显然：PcNP φ 数学的世纪难题，计算机科学领域的顶级难题：P=NP? 目前的研究结果倾向于认为：P!=NP 即：有些问题就是（不可快速计算的）难处理的问题 通常将可以由多项式时间的算法解决的问题看作是易处理的
P和NP P和NP都是问题的集合 P是所有可在多项式时间内用确定算法求解的判定问题的集合 ⚫ 对于一个问题X，若存在一个算法XSolver，能在O(nk )时间 内求解（k为某个常数），那么就称这个问题属于P NP是所有可用多项式时间算法验证其猜测准确性的问题的集合 ⚫ 对于一个问题X，若存在一个算法XChecker，能在多项式 时间复杂度内给出验证结果，那么就称这个问题属于NP 显然： 数学的世纪难题，计算机科学领域的顶级难题： P = NP ? ⚫ 目前的研究结果倾向于认为：P!=NP ⚫ 即：有些问题就是（不可快速计算的）难处理的问题 ⚫ 通常将可以由多项式时间的算法解决的问题看作是易处理的 P NP
计算复杂性的层次结构 EXP NPL nhn... NONDET (part of DET 2) NONDET (part of DET 2) 20 224
计算复杂性的层次结构
NPC:NP-Complete NP-Complete的非形式化定义 如果一个问题属于NP Φ且该问题与NP中的任何问题是一样难(hard)的 则称该问题属于NPC,或称之为NP完全的(NP-Complete) 3 研究NP完全问题的意义 ΦNPC问题是20世纪的最伟大的发现之一 ·1971年，Cook发现所有的NP问题都可以规约到SAT问题 1972年，Karp证明了21种问题是NP完全的 ⊕ 直接推论：如果任何一个NPC问题可以在多项式时间内解决 。则NP中的所有问题都有一个多项式时间的算法 Φ迄今尚未发现任何一个NPC问题的多项式时间解决方案
NPC：NP-Complete NP-Complete的非形式化定义 如果一个问题属于NP 且该问题与NP中的任何问题是一样难（hard）的 则称该问题属于NPC，或称之为NP完全的（ NP-Complete ） 研究NP完全问题的意义 NPC问题是20世纪的最伟大的发现之一 ⚫ 1971年，Cook发现所有的NP问题都可以规约到SAT问题 ⚫ 1972年，Karp证明了21种问题是NP完全的 直接推论：如果任何一个NPC问题可以在多项式时间内解决 ⚫ 则NP中的所有问题都有一个多项式时间的算法 迄今尚未发现任何一个NPC问题的多项式时间解决方案