Seminar #39

本周我们将在【线上】为大家带来计科92班李嘉图同学关于计算复杂性理论的报告！

• 李嘉图

  李嘉图同学是2019级（计科92）本科生。本次Seminar，他将分享春研期间在英国华威大学Igor C. Oliveira助理教授指导下进行的关于计算复杂性下界不可证明性的研究。证明无条件计算复杂度下界，如NP≠P或电路复杂度下界是计算复杂度理论中重要的开放问题。但经过数十年的探索，我们目前仍缺少能够解决这些基本问题的工具。这启发我们研究证明计算复杂性下界的元数学难度，即说明计算复杂性下界在某些数学理论中的不可证明性。在本次报告中，李嘉图同学将向大家介绍如何在有界算术（Bounded Arithmetic）这一皮亚诺算术（Peano Arithmetic）的重要片段中证明计算复杂性下界的不可证明性，以及有界算术中可证性的一个博弈论意义上的刻画。 欢迎全体姚班同学参加！

• 【重复一遍时间地点】北京时间 12.18 周日 下午 19:00-20:00 点击此处进行时区转换
• 【腾讯会议】 608-710-427