3-SAT最多有几个满足解？

姜咏江

朋友让我去看每年的The international SAT Competitions web page，看了一些数据没搞清楚竞赛的基础。总之没有有效的SAT解法，不想费更多时间去了解其中的事情了。

就3-SAT来说，最多能有多少个满足解？通过子句分段消去法理论可知，都是相互独立的子句块组成的3-SAT，每个子句块有1个子句的时侯，子句块解最多，有7个。n个逻辑变量构成的无恒一子句（恒一子句不影响求满足解）的3-CNF有m=[n/3]个独立的子句块时，那么最多应该有7^m个3-SAT的满足解。例如。n=99，则m=33，解最多的数量是7³³=7730993719707444524137094407个。

如果是上万个变量，子句块之间独立，那么3-SAT解的数量之多可想而知。不知道The international SAT Competitions的意义在何处。

2015-10-18