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