可满足性问题

可满足性问题(Boolean Satisfiability Problem)，简称SAT问题，源于数理逻辑中经典命题逻辑关于公式的可满足性的概念，是理论计算机科学中一个重要的问题，也是第一个被证明的NP-complete问题，对SAT问题的理论研究具有很多重要的意义。