当前位置: 首页 > 新闻中心 > 学术活动 > 正文

College Colloquium——Algebraic input models to NP-complete problems

发布日期:2024-01-15点击数:

报告人:万大庆(美国加州大学)

时间:2024年01月16日 10:00-

地址:理科楼LA103


摘要:The most important problem in theoretical computer science is the P vis NP problem, which says that any NP-complete problem cannot be solved in polynomial time. This, however, depends on the range of the input parameters. In the first part, we illustrate this with the usual dense input model for the subset sum problem. In the second part, we introduce an algebraic input model which makes the problem even harder, and yet one can prove that there is a polynomial time algorithm for a much larger range of input parameters. The proof depends crucially on a good estimate of exponential sums over the image set of polynomial map, which in turn depends on the Weil conjectures.


简介:万大庆,美国加州大学尔湾分校教授。研究方向:数论和算术代数几何,尤其是有限域上的zeta函数和L-函数,解决了现代数论中的若干著名猜想,在数学顶尖期刊《Annals of Mathematic》,《Invent. Math.》,《J. Amer. Math. Soc.》上发表多篇文章,其研究工作在算术代数几何的许多重要领域产生了重要影响。近年来,万教授在计算数论、编码和计算复杂性领域也做出了杰出的工作,其结果发表在FOCS、STOC、FOCM、IEEE IT等计算机和信息理论的顶级杂志上。现为国际著名数学杂志《Journal of Number Theory》和《Finite Fields and Their Applications》的编委。


邀请人:孔德荣


欢迎广大师生积极参与!



关于我们
重庆大学数学与统计学院的前身是始建于1929年的重庆大学理学院和1937年建立的重庆大学商学院,理学院是重庆大学最早设立的三个学院之一,首任院长为数学家何鲁先生。