【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
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。

  1. 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!

    0

    回复

  2. 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!

    0

    回复

  3. g

    It’s amazing in support of me to have a web page, which is valuable
    in support of my know-how. thanks admin

    0

    回复

  4. g

    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.

    0

    回复