NP难，符号问题和维度灾难——第四类数值方法？
数学公众报告
报告题目(Title)：NP难，符号问题和维度灾难——第四类数值方法？
报告人(Speaker)：邵嗣烘 (北京大学)
地点(Place)：后主楼1124
时间(Time)：2021年10月22日下午4-5点
邀请人(Inviter)：陈华杰
报告摘要
作为计算数学的主要研究方向，微分方程数值解在近100年的发展中取得了巨大的成功，汇成了三大类数值方法：50年代的差分方法，60年代的有限元方法和70年代的谱方法。这三类方法的收敛性都依赖于解的正则性，而且要达到最优的收敛阶往往需要精心调配网格。当试图用基于网格的方法去求解高维微分方程时就会遇到所谓的维度灾难（curse of dimensionality）。当数据科学和人工智能的热潮涌来时，情况变得更糟糕，因为可能再也没有微分方程可解了，而是需要直接去面对数据，正则性可能无从谈起，高维度更是与生俱来。本次报告将谈谈我们小组在面对上述困境时做的尝试。我们将从NP难的图割问题出发说说如何从连续的观点去看离散的问题（包括发展组合问题的临界点理论和求解NP难问题的谱方法等），之后以高维相空间内的多体Wigner量子动力学模拟为例谈谈如何用随机的观点去看确定的问题进而产生求解高维问题的分枝随机游走算法。其中，我们将展示符号问题（sign problem）的维度灾难（即方差随维度增加指数增长），而符号问题本质上又是NP难的。于是，在P和NP关系不清楚的当下，我们只能试图去寻找缓解符号问题的策略，包括使用驻相逼近 (stationary phase approximation) 和偏差理论（discrepancy theory）。一句话总结就是我们想去寻找第四类可能的数值方法来突破困境。
