报告 人：徐俊明
报告题目：复杂性理论（一）
报告时间：5月11号下午15:00（周三），5月13号下午15:00（周五）
报告题目：复杂性理论（二）
报告时间：5月16号下午15：00（周一），5月18号下午15:00（周三），5月20号下午15:00（周五）
报告题目：复杂性理论（三）
报告时间：5月23日下午15:00（周一），5月25日下午15:00（周三），5月27日下午15:00（周五）
报告地点：静远楼1506学术报告厅
主办单位：数学与统计学院、科技处
报告简介：
随着计算机的普及与发展，越来越多实际问题的解决需要借助于计算机，问题解决的速度取决于算法。对于一个问题π，如果存在一个多项式算法来解决它，则称π为P问题；如果目前还不存在一个多项式算法来解决它，但对于该问题的具体实例和一个猜想的结果，存在一个多项式算法来验证这个猜想的结果正确与否，则称π为NP问题。千禧年大奖难题之一：N=NP？目前还不能解决这个难题。本课程是在P≠NP的假定下，研究NP问题之间的关系，即NP完备性。主要内容：NP完备性的基本概念和理论，NP完备性的证明，NP完备性分析，NP难度，NP完备问题的处理方法以及与NP完备性有关的其它问题。作为实例，介绍图论和它的应用中一些著名的NP完备问题，如Hamilton问题、独立集问题、着色问题等。通过此课程的学习，使听众对NP完备性理论、问题的困难程度、证明方法和处理方式有个初步了解，学会分析处理一些具体问题基本思路。本课程不涉及高深的数学知识，所用实例以图论和优化问题为主，因此，要求听众对图论和优化有个基本的了解。
个人简介：
徐俊明，中国科学技术大学数学科学学院二级教授、博士生导师、中国运筹学会第七、八届理事，中国数学会组合与图论专业委员会第一、二、三届理事, 《运筹学学报》常务编委。先后访问过法国巴黎南大学、美国耶鲁大学、中田纳西州立大学、得克萨斯大学达拉斯分校。获“宝钢优秀教师奖”（2007年），中科院首届教学成果二等奖（2008年），指导培养研究生50多名，其中博士研究生23名，2名获“求实奖”，3名获“中科院院长奖”。长期从事图论和组合网络理论的教学和研究工作，发表学术论文200多篇，著有《图论及其应用》（中英文版）《组合网络理论》（中英文版），其中《图论及其应用》（中文版）被教育部批准为全国研究生指定教材（2002年）。
