问如何将SAT公式转换为3SAT格式？
EN

Stack Overflow用户

提问于 2021-04-16 09:48:28

回答 1查看 73关注 0票数 1

我很难理解什么是NP补全。因为我的一位教授没有很好地向我解释他们给我们的这个例子问题。如果有人知道这个解决方案，请给我解释一下，这样我就可以学习了。Here the equation that I was having trouble on! Please take a look.

发布于 2021-04-16 10:07:34

如果你有一个字面量太少的子句C，可以用(C∨x)∧(C∨x‘)替换，其中x是一个新变量。

如果你有一个包含太多文字的子句C，你可以首先将它拆分为C= C0和C1，一半的文字放在C0中，另一半的文字放在C1中，然后通过用(C0∨x)∧(C1∨x‘)替换C来返回到合取范式。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/67118064

复制

相似问题

问如何将SAT公式转换为3SAT格式？EN