内容提要 ·计算模型与计算复杂度关系 NP完全性理论介绍 ·问题分类:【P】与【NP】类 NP一难【hard】问题,NP完全集 清华大学 ·第一个NPC问题和NPC问题集 宋斌恒 ·如何证明一个问题是NPC问题 清华大学宋域恒 请华大学宋恒 引言 NPC问题 ·脑力劳动机械化【吴文俊先生】 ·P一NP一NPC问题定义及其猜想:NPC是 图灵机的停机问题:是否存在一个图灵机,他 类不可以在多项式时间内计算的问 可以回答其它图灵机是否停机【既算法是有界 题 的】 原则上是否存在一般数学问题的解题步骤的判 ·如果在量子计算模型中上述问题又如 决问题【希尔波特第十问题变种】 图灵公理:凡是可计算的函数都可以用一台图 灵机来计算 清华大学末斌恒 请华大学宋恒 下面介绍计算机械化的进程 明代数学家程大位著《算法统 宗》中关于珠算的插图 :a(m/ 清华大学末破恒 请华大学宋1 清华大学 宋斌恒 1 NP完全性理论介绍 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 • 计算模型与计算复杂度关系 • 问题分类：【P】与【NP】类 • NP－难【hard】问题，NP完全集 • 第一个NPC问题和NPC问题集 • 如何证明一个问题是NPC问题 清华大学 宋斌恒 3 引言 • 脑力劳动机械化【吴文俊先生】 • 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 • 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题变种】 • 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算 清华大学 宋斌恒 4 NPC问题 • P－NP－NPC问题定义及其猜想：NPC是 一类不可以在多项式时间内计算的问 题。 • 如果在量子计算模型中上述问题又如 何？ 清华大学 宋斌恒 5 下面介绍计算机械化的进程 清华大学 宋斌恒 6 明代数学家程大位著《算法统 宗》中关于珠算的插图