algorithm - 任何 NP 到 SAT。如何做到这一点并证明这是可能的？

Question

让我们从这里开始:据说所有的NP问题都可以归结为SAT( bool 可满足性问题)。更准确地说是 Circuit SAT，因为像 NP 这样的所有决策问题都应该以答案Yes 或No 结束。

但是现在，如果我有一个随机的 NP 问题，如何构建一个 bool 电路来测试，如何对我的输入进行分组，什么样的门(AND、NOT、OR 等等)应该连接这些输入。所以基本上，我的问题是如何设计 boolean Circuit，它给出了 TRUE 或 FALSE 的答案。

最后，这个答案意味着什么。我理解 TRUE 是因为这个 NP 问题可以在多项式时间内 解决，而 FALSE 则不能，对吗？

我脑子里一片困惑，如果我在解释我的问题时犯了逻辑错误，请不要太离谱 :) 我希望你能理解。

期待答案。

Answer 1

我理解这种困惑，但您的理解并不完全是它的工作原理。

NP-hardness 是决策问题的限定条件，即答案为是或否的问题。如果我们想证明一个决策问题是 NP 难的，我们通过证明它至少和我们已经知道它是 NP 难的问题一样难来做到这一点，例如 SAT .

我们如何证明问题 A 至少和问题 B 一样难？好吧，我们可以将其表述为

if we can solve A, we can also solve B

因此，给定问题 B 的实例，我们将其转换为问题 A 的实例，使用我们对 A 的解决方案来解决它，然后将其转换回 B 的解决方案。假设两个对话都很简单，我们知道 A 不可能比 B 更容易，因为 A 的解决方案 也是 B 的解决方案。

---

因此您的理解倒退了。为了证明某个问题是 NP-hard 问题，我们要证明它至少和 SAT 一样难，也就是说，给定 SAT 的任意实例，将其转换为您的问题的实例，然后解决该问题。如果答案是"is"，则原始 SAT 问题是可满足的，否则不是。

---

现在，正如我在评论中所写，没有标准的方法来进行转换。您需要以某种方式操纵您的问题，使其“看起来像 SAT”，以便进行转换。对于一些比其他问题更容易的问题，但我认为这是 NP 硬度证明中最难的部分。

人们通常做的是寻找另一个问题，这个问题已经被认为是 NP-hard 问题，但看起来有点像他们自己的问题。这样，减少变得更容易一些。但它仍然需要大量的工作和创造力。我建议您查看一些现有证据，看看其他人是如何做到这一点的。