可满足性问题的精确算法和计算复杂性

摘要

可满足性(SAT)问题是计算机科学中最重要的理论研究和实际应用问题之一。文章从标准计算复杂性理论的角度论述SAT问题的精确算法和计算复杂性，主要论述算法的发展，分析算法(最坏情况)的复杂度，并探讨SAT问题的复杂度上限。对一些具有意义的算法结果进行了解释和分析，并讨论了算法的重要性，同时还介绍了近几年的相关研究进展。

关键词

可满足性 / SAT算法 / NP完全性 / 精确算法 / 计算复杂性理论