科研学术

　　近日，计算机科学与工程学院（网络空间安全学院）2017级本科生和肖鸣宇教授撰写的论文“A Fast Algorithm for SAT in Terms of Formula Length”被计算机科学理论方向重要国际会议SAT 2021接收，彭俊强为论文第一作者。SAT会议（The International Conferences on Theory and Applications of Satisfiability Testing）是研究命题可满足性问题（SAT问题）的重要会议。SAT问题是第一个被证明的NP完全问题，在复杂性理论里最重要的公开难题（P vs NP）中扮演着重要角色，也在人工智能、运筹学和电子设计工程等众多领域中有基础应用。2021年的SAT会议全球共接收了38篇论文。

　　该论文证明了一般的SAT问题能在O*(1.0646^L)时间内被解决，其中L是输入的布尔公式的总长度（即布尔公式中的文字总个数）。该经典问题的运行时间上界在过去几十年里一直被深入研究。作者通过设计新的分支算法，运用测量治之（Measure-and-Conquer）的分析技术，最终改进了Chen和Liu于2009年给出的结果。该问题最佳结果的改进历程如下表1所示。

　　彭俊强同学目前是电子科技大学计算机科学与工程学院大四年级本科生，他从2020年秋开始进入肖鸣宇教授带领的算法兴趣小组学习，通过半年时间的学习和研究，攻克了这个重要的算法难题。

　　电子科技大学算法兴趣小组是由肖鸣宇教授发起的一个面向全校师生开放的算法研讨小组。该小组以探索算法难题和解决重要的科学问题为宗旨，激发和培养学生及青年老师对算法和基础理论的兴趣，为算法及相关研究方向感兴趣的师生提供一个交流平台。该小组目前关注的研究方向包括：计算理论、图论与图算法、组合优化、机制设计与算法博弈论、近似与随机算法、精确与参数算法等。组里长期参与的学生均能发表一篇高水平论文，并且多名学生在程序设计竞赛和数学建模竞赛中取得非常优异的成绩，在ACM程序设计竞赛中，小组中有5人进入了世界总决赛；在IEEE极限编程竞赛中连续两次获得世界第二名，三次进入世界前十名。