减少0-1背包概率。到SAT的概率

有什么办法来减少0-1 knapsack problem到SAT problem合取规范构成？减少0-1背包概率。到SAT的概率

来源

2015-07-20 xuhdev

如果你试图证明0-1背包问题是NP-hard，那么减少需要在另一个方向去... –

@j_random_hacker不，我没有证明它... – xuhdev

你总是可以制定出实现加法器和比较器，然后打开的，其结果为连接性规范形式所必需的数字电路。您可以将电路转换为CNF形式，而不用通过组成表示电路小部分输出的中间变量以指数形式进行扩展。

电路的每个节点总计为a = f（b，c）其中a是输出，b和c是输入，f是一些简单的函数，如&或|。只有当f（b，c）的结果是真的时，才能创建一个真正的CNF函数，并且它不会太笨拙，因为它只有三个变量的函数。

您可以重写任何电路融入了大量形式= F（B，C）的条款和所有你有这些的CNF版本做的是和他们在一起。假设您想要解决输出为真，那么您只需将输出变量作为那个大AND的最终组件。

来源

2015-07-21 05:09:34 mcdowella

Can你给我一个例子？我认为'f'会是不平凡的？ – xuhdev

我在这里讨论的函数是2个输入位的基本二进制函数。它们只有16个，没有非常复杂的，实际上你只需要一个，NAND（a，b）=〜（a＆b）就可以从它们中构建所有可能的数字电路。见例如http://www.ee.ic.ac.uk/hp/staff/dmb/courses/dig2/5_Adder.pdf查看二进制逻辑建立加法器的例子。另请参阅https://en.wikipedia.org/wiki/Logic_gate – mcdowella

我认为您的意思是Tseitin转型，这是我错过的部分。谢谢！ – xuhdev

减少0-1背包概率。到SAT的概率

回答

相关问题