成电讲堂

　　11月15日，上海交通大学傅育熙教授邀授做客人力资源部教师发展中心“学术沙龙”，带来题为“The Complexity of Reachability”的学术报告。本次学术沙龙由计算机学院肖鸣宇教授主持，相关专业方向的老师和学生们参加了讲座。

　　傅育熙首先介绍了可达性问题的背景知识和发展前沿。可达性问题是指在一个系统中，一个状态能否转变为另一个状态的问题。可达性问题有众多的变种，但都可以归结为图上的某种联通问题。他说，可达性问题自1976年开始研究，至今学术界对其复杂度的上下界有了很好的认识。

　　随后，他介绍了自己团队最新研究的结果：可达性问题是属于Tower-hard复杂度类的。他向在座的同学老师们解释了什么是Tower-hard复杂度，Tower-hard复杂度的研究重要性，以及解决这个问题的关键在于转换为代数模型，通过线性代数的方法，寻找想要的解。

　　讲座后，在场师生也针对自身感兴趣的问题与傅育熙教授进行了深入探讨。

　　相关链接：

　　傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起在上海交通大学计算机系任职，现为上海交通大学特聘教授。研究领域为理论计算机科学，研究内容涉及程序理论、并发理论、等价性验证、可达性理论、交互理论。他是国家杰出青年基金获得者、上海市优秀学科带头人。2000-2009年任上海交通大学计算机系主任，2001-2013年任上海交通大学软件学院院长。学术兼职有：上海高校软件理论研究中心主任、国务院学位委员会第六届学科评议组成员（2010-2014）、上海市计算机学会理事长（2015-2018）、教育部计算机类专业教学指导委员会副主任（2013-2017，2018-2022），是Mathematical Structures in Computer Science的编委。