电子科技大学计算机(网安)学院算法与逻辑团队在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年给出的结果。