English
导航菜单
在最近一期的Journal of the ACM （JACM）上，计算机科学与工程系BASICS实验室的陈翌佳教授与德国弗莱堡大学数学系的Joerg Flum教授合作发表了题为“From almost optimal algorithms to logics for complexity classes via listings and a halting problem”（ Volume 59 Issue 4, August 2012）的论文。
该论文是关于理论计算机科学中的三个子领域：有限模型论、参数算法和证明复杂性间的一个令人吃惊的联系。有限模型论是计算复杂性理论和数理逻辑的交叉学科，其根本目标是通过逻辑方法来理解各种问题的计算复杂度。参数算法是一类较为新颖的高效算法，在数据库、形式化验证、图论问题上有着广泛的应用。而证明复杂性主要是研究常见的形式化证明系统的效率。传统上，这三个领域有着完全不同的研究对象、问题和方法，关心的人群也各不相同。陈翌佳和Joerg Flum的结果在某种程度上打破了这三个领域间的壁垒，证明了它们各自内部的一个公开问题事实上是等价的：Blass-Gurevich逻辑能够刻画多项式时间、一个特殊的图灵机停机问题存在较高效的算法、以及存在最简洁的命题逻辑证明系统。这个联系为解决这些问题提供了崭新的思路。虽然这个问题还没有彻底解决，该论文已经给出了在一个稍弱的假定下，上述三个问题的否定性结论。
JACM作为美国计算机协会（Association for Computing Machinery，简称ACM）的旗舰刊物，创刊于1954年。现每年出版6期，每期刊登5篇左右的文章，均为全世界范围内计算机领域最重要的研究结果，特别是强调那些在计算机科学子领域间，以及计算机科学与其它学科间的交叉成果。到目前为止，国内在该刊物上一共发表了三篇论文，前两篇均由现任美国哥伦比亚大学助理教授陈汐，在清华大学姚期智教授指导下攻读博士学位期间发表的。
地址：上海市东川路800号学院概况
邮编：200240 邮箱：seiee@sjtu.edu.cn
Copyright © 2022上海交通大学电子信息与电气工程学院 版权所有
欢迎关注上海诚聘英才公众号