数据与算法精品教学（陈健生）19 计算复杂性理论.pdfVIP

数据与算法 2014-2015年秋季学期 陈健生 jschenthu@tsinghua.edu.cn 清华大学电子工程系 1 计算复杂性理论 2  计算复杂性理论 计 ◦ 计算机科学的重要分支，旨在依据计算的难度对计 算问题进行分类，以及分析不同难度类别问题之间 算 的关联； 复 ◦ 发展历史 杂  1936年，Alan Turing提出的图灵机模型能够灵活的定 义计算； 性  1965年，Hartmanis和Stearns发表论文阐述了计算的 理 时间、空间复杂度的定义；  1965年，Edmonds提出多项式时间复杂度的问题； 论  1971年，Cook和Levin各自独立证明了NP-Complete 问 题的存在；  1972年，Karp发表论文证明了21个不同的组合优化和图 论问题属于NP-Complete ；  ... 3  图灵机(Turing Machine) 计 ◦ 英国数学家Alan Turing提出的一种抽象的计算 模型，可以用来描述任何有限的数学逻辑过程； 算 复 ◦ 图灵机的构成： 杂  划分成若干小格子的无限长度纸带(Tape)，每个格子上 包含一个来自有限字符表的符号； 性  一个读写头(Head)可以在纸袋上左右移动，能读出或改 理 写当前格子中的符号；  一套控制规则(Table)规定在当前机器所处状态以及当前 论 格子中符号的情况下，读写头下一步的动作，以及机器的 下一个状态；  一个状态寄存器(State Register)记录机器当前的状 态，状态数目是有限的，且存在特殊状态称为停机. 4  图灵机 计 ◦ 图灵机由一个七元组定义: 算 , Σ, Γ, , , , → （ ） 复 杂 性  ：图灵机状态的有限集合；  Σ：输入字母表，不包括空格； 理  Γ：纸带字母表，包括空格且Σ⊂Γ； 论  ：转移函数Γ→Γ左移，右移；  ：起始状态， ∈；  ：接受状态， ∈；  ：拒绝状态， ∈.