- 4
SAT和3-SAT
【SAT问题】
将布尔可满足性问题（Boolean satisfiability problem）叫做SAT：
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ，问存在满足的真值赋值吗？
例如，设有3个子句：(x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} ),那么如果让所有的变量都为1，则不能够满足所有的子句，因为第二个子句的值为0。
【3-SAT问题】
3-SAT问题也叫作三元可满足性问题。因为每个子句恰好包含三个项。
3-SAT问题可以描述为：
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ，每一个子句的长度为3，问存在满足的真值赋值吗？
0
【微信公众号同步博客文章】
This design is steller! You obviously know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Great job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool!
回复
I simply couldn’t leave your web site before suggesting that I really loved the usual information an individual provide in your guests? Is going to be back continuously in order to check for new posts, thanks!
回复
It’s amazing in support of me to have a web page, which is valuable
in support of my know-how. thanks admin
回复
Thank you for another informative site. Where else may just I get that type of info
written in such an ideal manner? I’ve a mission that I am simply now operating on, and I
have been on the look out for such info.
回复