算法与逻辑团队在理论计算机科学领域顶级期刊Information and Computation上发表研究成果

近日,我校计算机科学与工程学院(网络空间安全学院)算法与逻辑团队2021级博士生彭俊强以第一作者身份在CCF理论计算机科学领域A类期刊Information and Computation (I&C)上发表题为《Further improvements for SAT in terms of formula length》的论文。论文第二作者和通讯作者为肖鸣宇教授。 

该论文研究了著名的布尔可满足性问题(SAT问题)的算法与计算复杂性,得到该问题精确求解中,以问题输入CNF公式的总长度L为度量的当前最佳运行时间上界,改进了十余年前Chen和Liu于2009年给出的结果。本文给出的时间运行界和历史上该问题的运行时间界如表1中所示。

image.png

SAT问题是第一个被证明的NP完全问题,在计算复杂性理论里扮演着重要角色,也在人工智能、运筹学和电子设计工程等众多领域中有着重要且基础的应用。该经典问题的运行时间上界在过去几十年里一直被深入研究。作者们通过设计新的分支算法,并运用测量治之(Measure-and-Conquer)的分析技术深入分析,最终取得了这项突破。

彭俊强同学为计算机(网安)学院2021级直博研究生。他从本科阶段开始进入算法与逻辑团队学习,在肖鸣宇教授的指导下从事SAT及其相关问题的研究工作。在博士学习的前两年已经发表两篇CCF A类和一篇CCF B类论文。

算法与逻辑团队由欧洲科学院院士、新西兰院士Bakh Khoussainov教授和肖鸣宇教授共同组建,周毅副教授、郝东副教授和许超助理教授、日籍Toru Takisaka副研究员等多位老师参与。该团队致力于基础理论研究,以探索算法难题和解决重要的科学问题为宗旨,激发和培养学生及青年老师对算法和基础理论的兴趣,为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括:算法设计与分析(包括近似算法、参数算法、精确算法、在线算法等)、逻辑、图论与图算法、组合优化、算法工程、机制设计与算法博弈论、形式化方法与认证等。

团队以科研育人为首要任务,培养出了众多优秀的学生。近两年本科生第一作者在WWW、IJCAI、SODA、COCOON、Discrete Mathematics等CCF A类会议和重要刊物上发表5篇论文。除论文外,团队学生还在多项科技竞赛中斩获重要奖项,仅2023年上半年就获得2023年华为软件精英挑战赛全球总决赛冠军,2023年全国大学生数学竞赛(非数学类)全国第一名,IEEE极限编程竞赛世界第四名(第五次进入世界前十名)等。

论文链接:https://www.sciencedirect.com/science/article/pii/S0890540123000883

, ,