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

6 thoughts on “SAT和3-SAT

  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. 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
  4. Hello would you mind sharing which blog platform you’re using?

    I’m going to start my own blog soon but I’m having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs and I’m looking for something unique.
    P.S Sorry for getting off-topic but I had to ask!

    0

Leave a Reply

Your email address will not be published.