科研学术

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

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

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