计算复杂性基础
课程编码：0839X1M05007H
英文名称：Foundation of Computational Complexity Theory
课时：40
学分：2.00
课程属性：专业普及课
主讲教师：吕克伟等
教学目的要求
本课程是理论计算机科学专业的基础课。通过本课程的学习,使同学了解计算机解决各类问题的难易程度,掌握计算复杂性的基本概念和思想方法,为进一步学习关于理论计算机科学的一些相关研究方向的专业课程（如：理论密码学）打下坚实的理论基础。
预修课程
离散数学
大纲内容
第一章 引言-计算复杂性介绍 3学时
第1节 计算机与可计算理论简介
第2节 计算复杂性与应用简介
第二章 计算问题的算法实例 3学时
第1节 图论中问题与算法
第2节 逻辑中问题与算法
第3节 格中问题与算法
第三章 计算模型(I) 3学时
第1节 图灵机基础
第2节 多带图灵机、时间与空间
第3节 非确定图灵机
第四章 计算模型(II) 3学时
第1节 通用图灵机
第2节 递归语言与递归可枚举语言
第3节 不可判定性
第五章 计算复杂类 3学时
第1节 复杂类
第2节 分离定理
第3节 可达性方法
第六章 归约和完备性 3学时
第1节 归约、完备性
第2节 NP关系、自归约
第3节 Oracle图灵机
第七章 P与NP的广义定义 3学时
第1节 广义可求解复杂类、可验证复杂类
第2节 可求解复杂类与可验证复杂类间关系
第八章 几种高效归约 3学时
第1节 Cook归约、Karp归约
第2节 Levi归约与自归约
第九章 广义NP完备性、coNP与NP的交集、多项式时间分层 4学时
第1节 广义NP完备性
第2节 coNP与NP的交集
第3节 多项式时间分层
第十章 概率多项式时间算法 3学时
第1节 随机化算法概述、度量指标
第2节 双边错误、单边错误复杂类
第十一章 交互证明与零知识证明 3学时
第1节 交互证明概述与复杂类
第2节 零知识证明
第十二章 密码概念的形式化描述，基本密码构件 3学时
第1节 密码概念的形式化描述
第2节 基本密码构件
第十三章 安全计算 3学时
第1节 安全计算
参考书
1、
计算复杂性基础
吕克伟
2013年6月
国防工业出版社
课程教师信息
吕克伟,男,中国科学院大学岗位教师, 中国科学院信息工程研究所研究员副研究员,中国共产党党员,1970年5月生于山东省淄博市,一直从事代数学、理论密码学和计算复杂性研究,在国内外刊物及会议发表论50余篇,获得2004年北京市科技进步二等奖。
叶顶锋,男,中国科学院大学岗位教师, 中国科学院信息工程研究所研究员研究员,1966年12月生于四川隆昌市,一直从事代数学、应用密码学和计算复杂性研究,在国内外刊物及会议发表论10余篇,获得过国家科技进步二等奖数项。
黄桂芳,女,1979年10月出生于河北省唐山市。中国科学院大学岗位教师, 中国科学院信息工程研究所研究员副研究员,硕士生导师,中国共产党党员。一直从事理论密码学和计算复杂性研究,研究方向为密码协议（零知识证明）和后量子公钥密码算法。在国内外刊物及会议发表论20篇,主持国家自然科学基金等课题7项。