SAT问题求解综述

摘要

可满足性问题(Satisfiability Problem,简称SAT问题)涉及到逻辑学、图论、计算机科学和计算机工程等多个研究领域.随着SAT求解算法研究的发展,SAT求解器已经可以解决程序分析、EDA设计和密码分析等多个行业中的实际问题.当前,SAT求解算法主要有完备算法和不完备算法,这两种算法针对不同应用都有各自的特点.通过研究和分析可以看出,今后基于行业领域的SAT求解算法优化、自动化问题编码和SAT求解并行化,将成为SAT求解技术的未来发展方向.