计算复杂性基础
课程编码：1802030839X1P3003H
英文名称：Foundation of Computational Complexity Theory
课时：40
学分：2.00
课程属性：专业课
主讲教师：吕克伟等
教学目的要求
本课程是网络
空间理论专业课。通过本课程的学习,使同学了解计算机解决各类问题的难易程度,掌握计算复杂性的基本概念和思想方法,为进一步
学习关于理论计算机科学的一些相关研究方向的专业课程（如：
理论密码学等）打下坚实的理论基础。
预修课程
离散数学
大纲内容
第一章 引言-计算复杂性介绍 3学时 吕克伟
第1节 计算机与可计算理论
第2节 计算复杂性与应用
第二章 计算问题的算法实例 3学时 吕克伟
第1节 图论中问题与算法
第2节 逻辑中问题与算法
第3节 格中问题与算法
第三章 计算模型(1) 4学时 吕克伟
第1节 图灵机基础
第2节 多带图灵机、时间与空间
第3节 非确定图灵机
第四章 计算模型(2) 3学时 吕克伟
第1节 通用图灵机
第2节 递归语言与递归可枚举语言
第3节 不可判定性
第五章 计算复杂类 3学时 吕克伟
第1节 复杂类
第2节 分层定理
第3节 可达性方法
第六章 归约和完备性 2学时 吕克伟
第1节 归约、自归约
第2节 完备性、NP关系
第3节 Oracle图灵机
第七章 NP-完备问题、 coNP 10学时 黄桂芳
第1节 P与NP的广义定义
第2节 几种高效归约
第3节 coNP与NP
第4节 P/poly与多项式时间分层
第八章 概率多项式时间算法 3学时 黄桂芳
第1节 概率多项式时间算法
第九章 交互证明与零知识证明概述 3学时 黄桂芳
第1节 交互证明与零知识证明
第2节 基于NP问题的零知识证明
第十章 密码学的计算复杂性视角 6学时 吕克伟
第1节 单向函数与随机性
第2节 密码基础
第3节 安全协议
参考书
1、
计算复杂性理论@Computational Complexity: A Modern Approach@计算复杂性基础
O.Goldreich著，张薇、韩益亮、杨晓元译@S. Arora and B. Barak著@ 吕克伟编著
2015年11月@2012年3月@2013年6月。
国防工业出版社@世界图书出版公司@国防工业出版社
课程教师信息
吕克伟，男， 副研究员，中国共产党党员。1999年毕业于北京大学数学学院，一直从事代数学、理论密码学和计算复杂性研究，先后主持国家自然科学基金项目、国家重点研发计划子课题等科研项目，在国内外刊物及会议发表论50余篇，获得2004年北京市科技进步二等奖，2001年9月至今，先后讲授计算数论、计算复杂性基础和代数编码等专业课，讲授的《计算复杂性理论基础》被评为中国科学院大学2019年学院级研究生优秀课程。
黄桂芳：女,副研究员,硕士生导师。2009年毕业于中科院软件所信息安全国家重点实验室,2009至2011年在中科院信息安全国家重点实验室从事博士后研究,研究方向为密码协议的设计和分析。先后主持国家自然科学基金项目、国家重点研发计划子课题、中科院信工所密码基金、中国博士后基金项目等科研项目10项左右,参与国家和省部级科研项目多项。在国内外重要学术期刊和国际学术会议上发表论文15篇左右,培养指导硕士研究生3名。从2017年起,承担国科大研究生教学工作,先后担任《计算复杂性基础》、《密码协议》的授课教师