algorithm - 什么是 SAT，它有什么用处？

Question

最近在 Reddit 上看到一篇关于使用 SAT 解题的文章 [1]。这让我对“SAT”这个东西非常好奇。我阅读了维基百科文章，但我想请你们中的某个人用更通俗易懂的术语为我解释一下。

什么是 SAT，它有什么用处？可以用来遍历树结构吗？用于解析文本？为了换行 [2]？用于装箱 [3]？它是一种优化技术吗？

在相关说明中，我读到 NP vs P 是关于选择集合中的哪些数字总和为零与检查某些数字总和是否为零 - SAT 是否与此相关？

[1] http://www.reddit.com/r/programming/comments/pxpzd/solving_hexiom_really_fast_with_a_sat_solver/

[2] http://en.wikipedia.org/wiki/Line_wrap

[3] http://en.wikipedia.org/wiki/Bin_packing_problem

Answer 1

SAT 非常重要，因为它是 NP-Complete。要理解这意味着什么，您需要清楚地了解 Complexity 类。这是一个简短的摘要:

• P 是可以在多项式时间内解决(即快速)的所有问题的类别。

• NP 是可以在多项式时间内验证解决方案的所有问题的类别。这意味着找到一个给定的解决方案很快，但找到一个通常很慢(通常是指数时间)。当然除非问题出在 NP 的 P 部分(正如下面指出的 P 是 NP 的一部分，您可以轻松验证)。

然后是一组 NP 完全问题。该集合包含所有非常通用的问题，您可以解决这些问题而不是 NP 中的另一个问题(这称为将问题简化为另一个问题)。这意味着您可以将一个问题从一个域转换为另一个 NP 完全问题，让它得出答案并将答案转换回来。

然而，通常可以证明一个问题是 NP 完全的，但对于另一个给定的问题，转换是不清楚的。

SAT 非常好，因为它是 NP-Complete，即您可以解决它而不是 NP 中的任何其他问题，而且归约也不难做到。 TSP 是另一个 NP 完全问题，但转换通常要困难得多。

所以，是的，SAT 可用于解决您提到的所有这些问题。然而，这通常是不可行的。可行的地方是，当没有其他快速算法已知时，例如您提到的难题。在这种情况下，您不必为这个谜题开发算法，但可以使用任何高度优化的 SAT 求解器，您最终会为您的谜题找到一个合理的快速算法。

例如，遍历树结构非常简单，任何从 SAT 到 SAT 的转换很可能比直接编写遍历要复杂得多。