从3-SAT减少到图形问题

Question

我有一个问题，我试图将3-SAT减少到特定的图形问题，但我不确定我在减少中使用的东西。实际上，还原构建了两部分图，如果变量$ x_1 $在第1子句中，则存在边缘$（x_1，c_1）$，则该边缘的成本取决于变量$ x_1 $的真实性，成本1如果$ x_1 $为true，而在其他地方为0。我的问题：它是否允许减少，还是我应该将整个图形实例独立于变量所采用的值独立？

谢谢你们！

Answer 1

如果我正确理解您的问题，您会问您是否可以在真相分配改变构造的情况下构建减少。

简而言之，不。从问题$ a $减少到问题$ b $的全部要点是，我们可以使用$ b $的算法来解决$ a $ - 如果我们已经知道$ a $的解决方案，那么我们可以微不足道地减少它几乎是其他任何问题。

在您的特殊情况下，如果您已经知道了变量的真相分配，那么您已经回答了3-SAT实例的输入公式是否令人满意，您想要的是减少公式的减少，然后转动它进入图形问题的实例，在其中求解图形问题将告诉您如何在3个SAT实例中设置变量。