nctcs2017陆品燕教授特邀报告.doc

理论计算机科学 一门交叉学科 陆品燕 理论计算机科学研究中心 上海财经大学 理论计算机 数学 科学 理论计算机 经济学 技术 理论计算机 数学 科学 理论计算机 经济学 技术 数学 ? 理论计算机科学是数学的一个分支 ? 数学的三个要素 ? 定义 ? 定理 ? 证明 ? 1936年，图灵关于图灵机的论文 图灵机 ? 可计算与不可计算 ? 希尔伯特第十问题 （1900年国际数学家大会， 23个问题） ? 计算复杂性 NP vs P ? 世界七大数学难题之一 （千禧年大奖难题） ? 2006年国际数学家大会 ? NP完全理论，计算问题的分类 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 图同态问题 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? ? ? 二分定理 [Dyer, Greenhill 00] 图同态的计数问题的计算复杂性分为 ? 如果目标图的每个连通分支都是带自环的完全图或者 完全二分图，那么该计算问题是多项式时间可解的; ? 对于所有其他情况，该计算问题是#P完全的 图同态计数问题的代数表达 ?: ?? → ?? ?, ? ∈ ?? ? ?(?), ?(?) ∈ ?? #3-coloring H= 0 1 1 1 0 1 1 1 0 ?? ? = ? H(vi, vj) ? ?1,?2,…,??∈[?] ?,? ∈? 带权重的图同态问题 [Bulatov, Grohe 05] 二分定理 ? Spin systems in Statistic Physics ? Graphical models in machine learning H= 2 1 1 1 2 1 ?? ? = ? ?1,?2,…,??∈[?] ? ?,? ∈? H(vi, vj) 1 1 2 partition function 负权和复数权重? ? ? = 1 1 was an obstacle for while 1 ?1 ? Quantum spin systems? ? Determinant vs permanent ? Surprising tractable families due to algebraic cancelation. ?? ? = ? H(vi, vj) ? ?1,?2,…,??∈[?] ?,? ∈? 负权和复数权重 ? [Goldberg, Grohe, Jerrum ,Thurley 08] 实数 权重的二分定理 ? = 1 1 1 ?1 是多项式时间可计算的 ? [Cai, Chen, L. 10] 复数权重的完整二分定理 本人应丘成桐先生邀请在第五届国际华人数学家 大会上作一个45分种的特邀报告 理论计算机 数学 科学 理论计算机 经济学 技术 科学 ? 科学发现的基本方法 ? 实验 ? 推理 ? 计算 ? 自然科学与理论计算机的交叉 ? 生物信息学 ? 量子信息与量子计算 ? 统计物理 FKT算法 ? 三位统计物理学家Fisher, Kasteleyn, Temperley ? 计算平面图的完美匹配数目: 统计物理中双原子 分子(Diatomic molecule)结构的配分函数 ? 基于代数方法的多项式时间算法 全息算法 ? 图灵奖得主Valiant教授在2004年提出的新的设计 多项式时间算法的方法 ? 通过一个全息规约（本质上是一个基变换）把其 他问题规约到平面图上的完美匹配数 ? 然后通过FKT算法求解 从艺术到科学 ? [Cai, L. STOC 2007] Holographic Algorithms: from Art to Science ? 证明了一系列数学刻画定理 ? 通用的设计全息算法的系统方法 ? 《American Scientist》 专题报道 相变现象 ? 微观参数的连续变化引起宏观状态的突变 ? 水的三态，物质的磁性等等 ? 相变现象也在计算问题中出现 可满足性问题(SAT) 二状态自旋系统的配分函数 ? [Li, L., Yin 2012] 理论计算机 数学 科学 理论计算机 经济学 技术 计算经济学 ? 经济学中的计算问题 ? 计算视角下的经济学问题 ? 经济学视角下的计算问题 Turing ’