报告人：朱洪教授 复旦大学
报告题目：图同构问题的新进展
时 间：2015年11月19日 (星期四) 10:45 ~ 11:30
地 点：仓山校区成功楼603报告厅
主 办：福建省网络安全与密码技术重点实验室，数学与计算机科学学院
参加对象：计算机系教师、研究生
报告摘要：图同构问题是一个不确定多项式时间内可以判定的问题，但是它至今没有多项式时间算法，但是也不能证明它是不确定多项式时间内可以判定的问题类中最难解决的问题之一，即迄今为止没有证明它是NP-完全的。我们经常称它为NPI问题，即属于NP-中间(intermediate)类。最近，匈牙利计算机科学家Laszlo Babai, 美国芝加哥大学数学和计算机科学系教授，和他的博士生John Wilmes合作，似乎很有希望得到图同构问题的拟多项式时间算法，即运行时间大约是nO(log(n)), 该时间复杂度比多项式时间高，但是比一般的NP-完全问题的指数时间低得多，比原先的exp(√(n log n))时间算法，大大改进了。从而，这提醒我们图同构问题可能不是NP-完全问题。这个结果如果被证实为正确的话，它将被评估为近几年里计算机科学的重大突破(Big Breakthough)
朱洪将在此报告里，简述这一方面的进展。
专家简介：1961年毕业于复旦大学数学系，然后留校任教直至2005年9月退休。其中1980-82年在美国布朗大学进修二年。1993年升正教授，1997年任博士生导师。曾任中国计算机学会理论专委会副主任，算法和计算理论分会主任。还任中国人工智能学会离散数学专委会理事长，中国密码学会理事。
