算法| NP完全|问题4

问题3-SAT和2-SAT是

（A） 都在P （B） 两者都是NP完全的 （C） 分别是NP完全和P （D） 分别是不可判定的和NP完全的 答复: （C） 说明： 布尔可满足性问题（SAT）是一个决策问题，其实例是一个只使用AND、OR、NOT、变量和括号编写的布尔表达式。问题是：给定表达式，是否有一些真值和假值分配给变量，从而使整个表达式为真？如果一个命题逻辑公式的逻辑值可以以一种使公式为真的方式分配给它的变量，那么这个公式就是可满足的。

3-SAT和2-SAT是k-可满足性（k-SAT）或简单可满足性（SAT）的特例，当每个子句分别精确地包含k=3和k=2个文本时。

2-SAT是P，而3-SAT是NP完全。（见 这 （如需解释）

参考资料： http://en.wikipedia.org/wiki/Boolean_satisfiability_problem 这个问题的小测验